Subject: Re: [RRG] cache issues in LISP and CONS - it's bad . . .

From: Robin Whittle <[email-masked]>
Date: Thu, 18 Oct 2007 16:07:37 +1000

Hi Dan and Noel,

Dan wrote:

> The issue regarding packet drops with LISP and LISP-CONS has been
> brought up a few times on the list.
>
> Basically, packets are dropped for every ITR cache miss.  Since
> CONS mapping requests may take a long time to be satisfied, this
> may result in unacceptable service.

LISP-CONS, LISP-NERD and TRRP use ITRs which cache mapping data and
rely on a query system which spans the Internet to get fresh mapping
data.

I think that dropping packets - or delaying them while queries and
responses cross the planet - is not acceptable for the future
architecture of the Internet.

Each such exchange typically involves multiple packets being sent
and received, with delays and potential losses.  Each mapping
request could take a few seconds to resolve under difficult
circumstances, and half to one second under common circumstances.
Folks in US and Europe need to remember that other folks have longer
packet paths - such as 350ms round trip delays from Melbourne
Australia to the Netherlands under close to ideal circumstances.

DNS-style mapping lookups (LISP-NERD or TRRP) will often involve
multiple queries to find the right nameserver.  This is especially
so for IPv6, with the likelihood of having to row through 48 bits or
more, 4 bits at a time with TRRP or I think LISP-NERD.  There's no
way an ITR could cache all those intermediate nameservers, even for
IPv4.

An ITR might be required to drop a packet and query the global
system in these circumstances:

  1 - A uses DNS to find IP address of B, and B's domain name
      requires the query go to a nameserver which uses a
      LISP-etc. mapped address.

  2 - A is on a mapped address too, so for each request to a
      nameserver in the above query, the nameserver's ITR needs
      to do a LISP/TRRP CAR-CDR/DNS-like lookup to find the ETR
      by which A can be reached.

  3 - A's ITR needs to do another mapping lookup before A can
      send a packet to B.

  4 - B's response requires another lookup, since A is on a
      mapped address too.

Point 1 and 2 can occur in pairs for as many depths of nameserver
recursion as is required to get an answer.  For instance five or so
times to find the IP address of "aa.bb.cc.ee.ff.gg".

At every such query, the LISP or TRRP ITR drops the packet and the
higher layers have to time out and retry.  Here is an example of
establishing a TCP link to a host which is identified by a four
level domain www.xxx.com.au.

The client host A is on a LISP-mapped address, as are the
nameservers for .com.au and .xxx.com.au.

We assume the client host A has cached the address of the .au
nameserver, (this would not be the case for the less used TLDs) but
not of the nameserver for .com.au.  Likewise, we assume A's LISP-ITR
initially has no mapping for the address of the .com.au nameserver.

This is perhaps unrealistic, since we wouldn't expect the .com.au
nameservers to be on LISP-mapped addresses.  However the following
example is valid for a webserver of a department of a company or
university, such as:

   www.astro.someuni.ch
   www.sales.wizmo.es

where these organisations use mapped addresses for their networks.
This is especially the case in the future when LISP/Ivip-etc.-mapped
address space is likely to be very widely used.

For instance maybe someuni.ch runs one of its nameservers on its own
 LISP-etc.-mapped network and a second one on another university's
LISP-etc.-mapped network - but the astronomy department has a
separate campus with one of its nameservers on another portion of
LISP-etc.-mapped address space etc.

 A  -X-> ns1.com.au  LISP ITR drops the 1st packet.

                     A times out.  How long does the first time-out
                     take?

 A  ---> ns1.com.au  A sends a 2nd packet, which the ITR now has
                     mapping for (ideally - but maybe the ITR is
                     still awaiting a response from the global
                     CAR-CDR or DNS-like query system) and so
                     tunnels to the ETR which serves ns1.com.au.

 A <-X-  ns1.com.au  The LISP ITR near ns1.com.au drops the packet
                     - it has no mapping for A's address.

                     A times out again.  How long does the second
                     time-out take?

 A  ---> ns1.com.au  A sends a third packet.

                     Or has A given up on ns1 and tries to send
                     a query to ns2.com.au?  This is on a totally
                     different network, and so we REPEAT (not
                     shown here) all the above steps.

                     Now (ideally) the LISP ITR near A has mapping
                     information for nsx.com.au - so finally, A
                     gets its query to nsx.com.au.

 A <---  nsx.com.au  Ideally, the nameserver's ITR has mapping for
                     A by now, so the packet is tunneled to A's
                     ETR and reaches A.

          Repeat the same stuff (as detailed below) so that A can
          find out the address of the nameserver for xxx.com.au.

 A  -X-> ns1.xxx.com.au  A's 1st packet is dropped by the LISP ITR.

                         A times out.

 A  ---> ns1.xxx.com.au  A sends a 2nd packet.

 A <-X-  ns1.xxx.com.au  LISP ITR near ns1.xxx.com.au drops packet.

                         A times out again.

 A  ---> ns1.xxx.com.au  A sends a third packet.

 A <---  nsx.xxx.com.au  A receives the IP address of
                         www.xxx.com.au.

          Now a similar pattern of dropped packets and time-outs
          so that A establishes a TCP session with the web server.

          The web server isn't necessarily on the same LISP-mapped
          address space as the nameservers. It could be at a hosting
          company, which uses LISP-mapped space so it can move its
          upstream connections to other ISPs without all its
          customers having to change their DNS entries for their
          web servers.

 A  -X-> www.xxx.com.au  A's 1st packet dropped by LISP ITR.

                         A times out.

 A  ---> www.xxx.com.au  A sends a 2nd packet.  By now, ideally
                         A's ITR has the mapping data.

 A <-X-  www.xxx.com.au  LISP ITR near www.xxx.com.au drops
                         packet.

                         A times out again.  www.xxx.com.au has
                         a half-open TCP session dangling . . .

 A  ---> www.xxx.com.au  A sends a third packet.  The webserver
                         half-opens a second TCP session.

 A <---  www.xxx.com.au  A gets its TCP acknowledgement and
                         sends its response . . .

 A  ---> www.xxx.com.au  . . . which (ideally) will be tunneled
                         immediately.

This is arguably worse than some common circumstances, but it is
easy to think of more difficult cases, with a greater recursion of
nameservers.  Any packets dropped en-route make things still worse.

This is:

  16 packets sent (not counting flurry of ITR query traffic)

   6 dropped packets

   2 1st time-outs by A's name lookup code.

   2 2nd time-outs by A's name lookup code.

   1 1st time-out by A's TCP session establishment code.

   1 2nd time-out by A's TCP session establishment code.

With eFIT-APT or Ivip, there are no dropped packets and we have:

 A  ---> ns1.com.au
 A <---  nsx.com.au

 A  ---> ns1.xxx.com.au
 A <---  nsx.xxx.com.au

 A  ---> www.xxx.com.au
 A <---  www.xxx.com.au
 A  ---> www.xxx.com.au

   7 packets sent

   0 dropped packets

   0 time-outs

In this example, LISP or TRRP typically makes the user and higher
level protocols wait for 6 time-out periods.  I think this is really
unacceptable.

The delay would be less with only one level of DNS recursion, and if
only one end of each exchange using LISP-mapped address space.

If something like LISP or TRRP was introduced, I think people would
soon find that the address space it handles sucks - due to the
common experience of excessive delays in establishing sessions of
any kind.  It would be very much harder to convince people to adopt
this space if it means a permanent degradation of their own
experience and of every person who tries to communicate with them.

> Suggestions have been made to route packets on the old topology in
> the event of ITR cache misses. However, this leads to a major
> incremental deployment issue -- since LISP adopters will still
> need to maintain their routes in the old topology, there would be
> no reduction in the size of the global routing table.

I agree there would be no absolute reduction, but there could and
should still be less BGP prefixes than if LISP etc. was not
introduced.  I discuss this below in my response to Noel.

> I have not seen any other suggestions on how to handle this issue.
> Could this be a fundamental problem with the design, or are there
> other solutions?

It is a fundamental problem with having caching ITRs which can't let
a packet go to another ITR which has the full database, and where
the caching ITRs rely on a global-sized - and therefore slow and
unreliable - query system.

Eliot Lear proposed (RRG messages leading to 264 & 288) that
LISP-NERD could have one or more ITRs well outside the sending
host's ISP's network to catch those packets which are not caught by
an ITR in that network.  I think this amounts to the same thing as
Ivip's "multicast ITRs in the core".  I think this was meant as a
means of making LISP-NERD incrementally deployable.  Perhaps, if the
LISP-NERD ITRs were modified to pass the packets they couldn't
tunnel, this would mean that the packets would be tunnelled
immediately, rather than dropped.

In that case, LISP-NERD would resemble eFIT-APT and Ivip in having
some caching ITRs which could let packets go through to a full
database ITR (Default Mapper for eFIT-APT, or ITRD for Ivip) when
the caching ITR didn't have the mapping information.  Perhaps with
Eliot's suggestion, those "full database" ITRs are only
"full-database" for one BGP-prefix's range of destination addresses,
and perhaps there is only one such ITR for each such prefix, rather
than necessarily multiple of them using anycast.

As it stands, here is the situation as I understand it.  (Please
check later in this thread for corrections):

                    LISP-CONS  LISP-NERD  eFIT-APT Ivip    TRRP

Full DB ITRs?       No         No         Default  ITRD    No
                                          Mappers

Caching ITRs?       All        All        ITR      ITRC    All
                                                   ITFH

Local query         No         No         Default  QSD     No
servers for                               Mappers  QSC
caching ITRs?

Caching ITR must    Yes        Yes        No       No      Yes
drop packets it
has no mapping for?

Distribution of     Pull       Pull       Push     Push    Pull
database to         CAR-CDR    DNS-like   slow     fast    DNS-like
networks with       global     global     via      Repli-  global
ITRs etc.?          network    network    BGP      cator   network
                                                   system

Incremental                    RRG                 Yes
deployment via                 messages
"anycast ITRs in               264 & 288
the core"?

TRRP also has a method by which some ITRs (depending on how directly
they queried the authoritative DNS-like mapping information servers)
get push notification of changed mapping from the authoritative
mapping servers.  However I can't see how this would scale well.

eFIT-APT and Ivip are the only two proposals in which all packets
are tunneled without delay.

Noel Chiappa wrote, in part:

DJ> Suggestions have been made to route packets on the old topology
in the
DJ> event of ITR cache misses. However, this leads to a major
incremental
DJ> deployment issue -- since LISP adopters will still need to maintain
DJ> their routes in the old topology, there would be no reduction in the
DJ> size of the global routing table.
> 
> Well, it's not just an incremental issue; either i) we always maintain the
> backup routing (in which case we don't get the size reductions, as you point
> out), 

I disagree with this prevalent notion that maintaining a prefix in
BGP while that prefix is handled by an ITR-ETR mapping scheme will
not result in reductions in the size of the global BGP routing table.

This would only be true if every such prefix was used to serve a
single end-user network.  The major benefit of all these ITR-ETR
schemes is that they can slice and dice the address space much finer
than BPG, which is limited (for all practical purposes in the
foreseeable future) to 256 IP address chunks in IPv4.

If end-user networks all needed more than 128 IP addresses, then it
might be true that the ITR-ETR mapping systems can't help use IPv4
address space more efficiently.

However I believe there are a large and growing number of end-user
networks which require multihoming and/or address space which
doesn't change when a new ISP is used.  ("Serial multihoming" as
Iljitsch wrote - though call this "portable address space", with
apologies to those whose teeth itch at the mention of this phrase.)

On this list a few weeks ago, several other people supported my view
that there is a significant number of end-user networks with smaller
(than 128, I guess) IPv4 address requirements who would be well
served by LISP/eFIT-APT/Ivip/TRRP-mapped space, and who would
contribute to the growth of the global BGP routing table if such an
ITR-ETR mapping system was not introduced.

> or ii) we don't maintain them into the indefinite future, in which case
> the speedup of using the backup routing would not be available in the future.

As long as Ivip or whatever achieves benefits by enabling lots more
end-user networks to operate as they require without each one
getting their own BGP-advertised prefix, then I think there's no
need to worry about maintaining the larger (shorter) prefixes in BGP
when they are mapped by LISP etc.

> But since I think we can make the resolution adequately fast, I don't think
> there's a problem here.

You could probably create a complex combination of caching and
genuine push of update messages to make the CAR-CDR network faster.

The question is whether it would be easier to create a complex and
souped up CAR-CDR system than to establish a clean - although
ambitious - system to distribute mapping data globally, within a few
seconds, as I am planning with Ivip.

My current description of the Replicator system is broad, so it is
hard to make comparisons of difficulty and cost now.  Over the next
few months I hope to write up some more elegant, secure and concrete
details.

 - Robin

--
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: [email-masked]
Date: Thu, 18 Oct 2007 03:09:57 EDT

Obviously, this is a dead end street and I can only observe how this  
community walks to its very end.
There however the community might remember that according to Rekther's law  
there is also a second way.
 
Heiner

In einer eMail vom 18.10.2007 08:10:07 Westeuropäische Normalzeit schreibt  
[email-masked]:

Hi Dan  and Noel,

www.astro.someuni.ch
www.sales.wizmo.es

A times  out.

A times out  again.

A times out.

This is:

6 dropped packets

A  ---> ns1.com.au
A <---   nsx.com.au

A  ---> ns1.xxx.com.au
A <---   nsx.xxx.com.au

A  ---> www.xxx.com.au
A <---   www.xxx.com.au
A  ---> www.xxx.com.au

7 packets  sent

0 dropped packets

0  time-outs

Incremental           RRG           Yes
deployment via         messages

-  Robin

---

From: Eliot Lear <[email-masked]>
Date: Thu, 18 Oct 2007 19:42:16 +0200

Hi Robin,

Forgive a terse reply to a long message, but perhaps I didn't state my
own intentions very well in NERD.  At least initially, there should be
no reason to cache ANYTHING.  We simply are not yet at an inflection
point where we need to.  This is what the data will show.  If I were a
betting man, I might put money down on us not needing a cache mechanism
for many many years.  All of this presumes, of course, that you're
updating a database about once an hour.  You could break it up in
smaller increments, but I suspect that's a reasonable operational
provisioning period, with time to sign and process and all.  Hence,
off-host caching is not an issue with NERD in this case.

Now, suppose I lose my bet.  Then I would implement CONS or something
like it, and bifurcate the NERD database into regions, and use LISP for
things that are outside my region.  There is some configuration
complexity with this approach that I have not fully explored, like how
do you decide what region you're in, and which databases to use NERD for
and to use CONS for.  I suspect the answer to these questions lie in
having a meta-database that is retrieved, but I've not gone much further.

Eliot

---

From: Sheng Jiang <[email-masked]>
Date: Fri, 19 Oct 2007 09:30:48 +0800

Well, there may be other branch that seems been forgotten by all of us: the
future internet architecture, of course, needs a NEW mapping system. An
efficient, robust mapping system can reduce the cache issues a lot, maybe
into an acceptable scope.

DNS-style mapping system is more than 20 years old and was mainly designed
for the fixed network. It cannot meet the new requirements. If the future
internet architecture was established on such out-of-time technology, the
dead end could be expected.

A new mapping system should at least support: fast updating, synchronization
if distributed, real-time handover, choosing between multiple items, etc.
Furthermore, it must have a business model that supports it. One more
consideration is that it might support different ID/locator separate
proposals if we designed it carefully.

Best regards,

Dr. Sheng JIANG

IP Research Department, Networking Research Department, Network Product
Line, Huawei Technologies Co. Ltd.
*-----Original Message-----
*From: [email-masked] [mailto:[email-masked]] On Behalf Of Robin
Whittle
*Sent: Thursday, October 18, 2007 2:08 PM
*To: Routing Research Group list
*Cc: Noel Chiappa; Dan Jen
*Subject: Re: [RRG] cache issues in LISP and CONS - it's bad . . .
*
*Hi Dan and Noel,
*
*Dan wrote:
*
*> The issue regarding packet drops with LISP and LISP-CONS has been
*> brought up a few times on the list.
*>
*> Basically, packets are dropped for every ITR cache miss.  Since
*> CONS mapping requests may take a long time to be satisfied, this
*> may result in unacceptable service.
*
*LISP-CONS, LISP-NERD and TRRP use ITRs which cache mapping data and
*rely on a query system which spans the Internet to get fresh mapping
*data.
*
*I think that dropping packets - or delaying them while queries and
*responses cross the planet - is not acceptable for the future
*architecture of the Internet.
*
*Each such exchange typically involves multiple packets being sent
*and received, with delays and potential losses.  Each mapping
*request could take a few seconds to resolve under difficult
*circumstances, and half to one second under common circumstances.
*Folks in US and Europe need to remember that other folks have longer
*packet paths - such as 350ms round trip delays from Melbourne
*Australia to the Netherlands under close to ideal circumstances.
*
*DNS-style mapping lookups (LISP-NERD or TRRP) will often involve
*multiple queries to find the right nameserver.  This is especially
*so for IPv6, with the likelihood of having to row through 48 bits or
*more, 4 bits at a time with TRRP or I think LISP-NERD.  There's no
*way an ITR could cache all those intermediate nameservers, even for
*IPv4.
*
*An ITR might be required to drop a packet and query the global
*system in these circumstances:
*
*  1 - A uses DNS to find IP address of B, and B's domain name
*      requires the query go to a nameserver which uses a
*      LISP-etc. mapped address.
*
*  2 - A is on a mapped address too, so for each request to a
*      nameserver in the above query, the nameserver's ITR needs
*      to do a LISP/TRRP CAR-CDR/DNS-like lookup to find the ETR
*      by which A can be reached.
*
*  3 - A's ITR needs to do another mapping lookup before A can
*      send a packet to B.
*
*  4 - B's response requires another lookup, since A is on a
*      mapped address too.
*
*Point 1 and 2 can occur in pairs for as many depths of nameserver
*recursion as is required to get an answer.  For instance five or so
*times to find the IP address of "aa.bb.cc.ee.ff.gg".
*
*At every such query, the LISP or TRRP ITR drops the packet and the
*higher layers have to time out and retry.  Here is an example of
*establishing a TCP link to a host which is identified by a four
*level domain www.xxx.com.au.
*
*The client host A is on a LISP-mapped address, as are the
*nameservers for .com.au and .xxx.com.au.
*
*We assume the client host A has cached the address of the .au
*nameserver, (this would not be the case for the less used TLDs) but
*not of the nameserver for .com.au.  Likewise, we assume A's LISP-ITR
*initially has no mapping for the address of the .com.au nameserver.
*
*This is perhaps unrealistic, since we wouldn't expect the .com.au
*nameservers to be on LISP-mapped addresses.  However the following
*example is valid for a webserver of a department of a company or
*university, such as:
*
*   www.astro.someuni.ch
*   www.sales.wizmo.es
*
*where these organisations use mapped addresses for their networks.
*This is especially the case in the future when LISP/Ivip-etc.-mapped
*address space is likely to be very widely used.
*
*For instance maybe someuni.ch runs one of its nameservers on its own
* LISP-etc.-mapped network and a second one on another university's
*LISP-etc.-mapped network - but the astronomy department has a
*separate campus with one of its nameservers on another portion of
*LISP-etc.-mapped address space etc.
*
*
* A  -X-> ns1.com.au  LISP ITR drops the 1st packet.
*
*                     A times out.  How long does the first time-out
*                     take?
*
* A  ---> ns1.com.au  A sends a 2nd packet, which the ITR now has
*                     mapping for (ideally - but maybe the ITR is
*                     still awaiting a response from the global
*                     CAR-CDR or DNS-like query system) and so
*                     tunnels to the ETR which serves ns1.com.au.
*
* A <-X-  ns1.com.au  The LISP ITR near ns1.com.au drops the packet
*                     - it has no mapping for A's address.
*
*                     A times out again.  How long does the second
*                     time-out take?
*
* A  ---> ns1.com.au  A sends a third packet.
*
*                     Or has A given up on ns1 and tries to send
*                     a query to ns2.com.au?  This is on a totally
*                     different network, and so we REPEAT (not
*                     shown here) all the above steps.
*
*                     Now (ideally) the LISP ITR near A has mapping
*                     information for nsx.com.au - so finally, A
*                     gets its query to nsx.com.au.
*
* A <---  nsx.com.au  Ideally, the nameserver's ITR has mapping for
*                     A by now, so the packet is tunneled to A's
*                     ETR and reaches A.
*
*          Repeat the same stuff (as detailed below) so that A can
*          find out the address of the nameserver for xxx.com.au.
*
* A  -X-> ns1.xxx.com.au  A's 1st packet is dropped by the LISP ITR.
*
*                         A times out.
*
* A  ---> ns1.xxx.com.au  A sends a 2nd packet.
*
* A <-X-  ns1.xxx.com.au  LISP ITR near ns1.xxx.com.au drops packet.
*
*                         A times out again.
*
* A  ---> ns1.xxx.com.au  A sends a third packet.
*
* A <---  nsx.xxx.com.au  A receives the IP address of
*                         www.xxx.com.au.
*
*          Now a similar pattern of dropped packets and time-outs
*          so that A establishes a TCP session with the web server.
*
*          The web server isn't necessarily on the same LISP-mapped
*          address space as the nameservers. It could be at a hosting
*          company, which uses LISP-mapped space so it can move its
*          upstream connections to other ISPs without all its
*          customers having to change their DNS entries for their
*          web servers.
*
* A  -X-> www.xxx.com.au  A's 1st packet dropped by LISP ITR.
*
*                         A times out.
*
* A  ---> www.xxx.com.au  A sends a 2nd packet.  By now, ideally
*                         A's ITR has the mapping data.
*
* A <-X-  www.xxx.com.au  LISP ITR near www.xxx.com.au drops
*                         packet.
*
*                         A times out again.  www.xxx.com.au has
*                         a half-open TCP session dangling . . .
*
* A  ---> www.xxx.com.au  A sends a third packet.  The webserver
*                         half-opens a second TCP session.
*
* A <---  www.xxx.com.au  A gets its TCP acknowledgement and
*                         sends its response . . .
*
* A  ---> www.xxx.com.au  . . . which (ideally) will be tunneled
*                         immediately.
*
*This is arguably worse than some common circumstances, but it is
*easy to think of more difficult cases, with a greater recursion of
*nameservers.  Any packets dropped en-route make things still worse.
*
*This is:
*
*  16 packets sent (not counting flurry of ITR query traffic)
*
*   6 dropped packets
*
*   2 1st time-outs by A's name lookup code.
*
*   2 2nd time-outs by A's name lookup code.
*
*   1 1st time-out by A's TCP session establishment code.
*
*   1 2nd time-out by A's TCP session establishment code.
*
*
*With eFIT-APT or Ivip, there are no dropped packets and we have:
*
* A  ---> ns1.com.au
* A <---  nsx.com.au
*
* A  ---> ns1.xxx.com.au
* A <---  nsx.xxx.com.au
*
* A  ---> www.xxx.com.au
* A <---  www.xxx.com.au
* A  ---> www.xxx.com.au
*
*   7 packets sent
*
*   0 dropped packets
*
*   0 time-outs
*
*In this example, LISP or TRRP typically makes the user and higher
*level protocols wait for 6 time-out periods.  I think this is really
*unacceptable.
*
*The delay would be less with only one level of DNS recursion, and if
*only one end of each exchange using LISP-mapped address space.
*
*If something like LISP or TRRP was introduced, I think people would
*soon find that the address space it handles sucks - due to the
*common experience of excessive delays in establishing sessions of
*any kind.  It would be very much harder to convince people to adopt
*this space if it means a permanent degradation of their own
*experience and of every person who tries to communicate with them.
*
*
*> Suggestions have been made to route packets on the old topology in
*> the event of ITR cache misses. However, this leads to a major
*> incremental deployment issue -- since LISP adopters will still
*> need to maintain their routes in the old topology, there would be
*> no reduction in the size of the global routing table.
*
*I agree there would be no absolute reduction, but there could and
*should still be less BGP prefixes than if LISP etc. was not
*introduced.  I discuss this below in my response to Noel.
*
*> I have not seen any other suggestions on how to handle this issue.
*> Could this be a fundamental problem with the design, or are there
*> other solutions?
*
*It is a fundamental problem with having caching ITRs which can't let
*a packet go to another ITR which has the full database, and where
*the caching ITRs rely on a global-sized - and therefore slow and
*unreliable - query system.
*
*Eliot Lear proposed (RRG messages leading to 264 & 288) that
*LISP-NERD could have one or more ITRs well outside the sending
*host's ISP's network to catch those packets which are not caught by
*an ITR in that network.  I think this amounts to the same thing as
*Ivip's "multicast ITRs in the core".  I think this was meant as a
*means of making LISP-NERD incrementally deployable.  Perhaps, if the
*LISP-NERD ITRs were modified to pass the packets they couldn't
*tunnel, this would mean that the packets would be tunnelled
*immediately, rather than dropped.
*
*In that case, LISP-NERD would resemble eFIT-APT and Ivip in having
*some caching ITRs which could let packets go through to a full
*database ITR (Default Mapper for eFIT-APT, or ITRD for Ivip) when
*the caching ITR didn't have the mapping information.  Perhaps with
*Eliot's suggestion, those "full database" ITRs are only
*"full-database" for one BGP-prefix's range of destination addresses,
*and perhaps there is only one such ITR for each such prefix, rather
*than necessarily multiple of them using anycast.
*
*As it stands, here is the situation as I understand it.  (Please
*check later in this thread for corrections):
*
*                    LISP-CONS  LISP-NERD  eFIT-APT Ivip    TRRP
*
*Full DB ITRs?       No         No         Default  ITRD    No
*                                          Mappers
*
*Caching ITRs?       All        All        ITR      ITRC    All
*                                                   ITFH
*
*Local query         No         No         Default  QSD     No
*servers for                               Mappers  QSC
*caching ITRs?
*
*Caching ITR must    Yes        Yes        No       No      Yes
*drop packets it
*has no mapping for?
*
*Distribution of     Pull       Pull       Push     Push    Pull
*database to         CAR-CDR    DNS-like   slow     fast    DNS-like
*networks with       global     global     via      Repli-  global
*ITRs etc.?          network    network    BGP      cator   network
*                                                   system
*
*Incremental                    RRG                 Yes
*deployment via                 messages
*"anycast ITRs in               264 & 288
*the core"?
*
*
*TRRP also has a method by which some ITRs (depending on how directly
*they queried the authoritative DNS-like mapping information servers)
*get push notification of changed mapping from the authoritative
*mapping servers.  However I can't see how this would scale well.
*
*eFIT-APT and Ivip are the only two proposals in which all packets
*are tunneled without delay.
*
*
*Noel Chiappa wrote, in part:
*
*DJ> Suggestions have been made to route packets on the old topology
*in the
*DJ> event of ITR cache misses. However, this leads to a major
*incremental
*DJ> deployment issue -- since LISP adopters will still need to maintain
*DJ> their routes in the old topology, there would be no reduction in the
*DJ> size of the global routing table.
*>
*> Well, it's not just an incremental issue; either i) we always maintain
the
*> backup routing (in which case we don't get the size reductions, as you
point
*> out),
*
*I disagree with this prevalent notion that maintaining a prefix in
*BGP while that prefix is handled by an ITR-ETR mapping scheme will
*not result in reductions in the size of the global BGP routing table.
*
*This would only be true if every such prefix was used to serve a
*single end-user network.  The major benefit of all these ITR-ETR
*schemes is that they can slice and dice the address space much finer
*than BPG, which is limited (for all practical purposes in the
*foreseeable future) to 256 IP address chunks in IPv4.
*
*If end-user networks all needed more than 128 IP addresses, then it
*might be true that the ITR-ETR mapping systems can't help use IPv4
*address space more efficiently.
*
*However I believe there are a large and growing number of end-user
*networks which require multihoming and/or address space which
*doesn't change when a new ISP is used.  ("Serial multihoming" as
*Iljitsch wrote - though call this "portable address space", with
*apologies to those whose teeth itch at the mention of this phrase.)
*
*On this list a few weeks ago, several other people supported my view
*that there is a significant number of end-user networks with smaller
*(than 128, I guess) IPv4 address requirements who would be well
*served by LISP/eFIT-APT/Ivip/TRRP-mapped space, and who would
*contribute to the growth of the global BGP routing table if such an
*ITR-ETR mapping system was not introduced.
*
*
*> or ii) we don't maintain them into the indefinite future, in which case
*> the speedup of using the backup routing would not be available in the
future.
*
*As long as Ivip or whatever achieves benefits by enabling lots more
*end-user networks to operate as they require without each one
*getting their own BGP-advertised prefix, then I think there's no
*need to worry about maintaining the larger (shorter) prefixes in BGP
*when they are mapped by LISP etc.
*
*
*> But since I think we can make the resolution adequately fast, I don't
think
*> there's a problem here.
*
*You could probably create a complex combination of caching and
*genuine push of update messages to make the CAR-CDR network faster.
*
*The question is whether it would be easier to create a complex and
*souped up CAR-CDR system than to establish a clean - although
*ambitious - system to distribute mapping data globally, within a few
*seconds, as I am planning with Ivip.
*
*My current description of the Replicator system is broad, so it is
*hard to make comparisons of difficulty and cost now.  Over the next
*few months I hope to write up some more elegant, secure and concrete
*details.
*
* - Robin
*
*
*--
*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: Fri, 19 Oct 2007 14:33:15 +1000

I am correcting some things I wrote about LISP-NERD in an earlier
message - and replying to Eliot Lear and Sheng Jiang.

Hi Eliot,

I apologise for some of the things I have written on the list about
LISP-NERD recently being wrong.  I was writing from my own memory,
which has clearly become garbled - because I wrote that NERD
involved caching and querying in a DNS-like fashion.  I did know
better than this!

Here is new version of the comparison table, with hopefully correct
details for LISP-NERD.

This will look like garbage unless displayed in a fixed width font.

Full DB ITRs?       No*        Yes        Default  ITRD    No
                                          Mappers

Caching ITRs?       All*       No         ITR      ITRC    All
                                                   ITFH

Local query         No*                   Default  QSD     No
servers for                               Mappers  QSC
caching ITRs?

Caching ITR must    Yes                   No       No      Yes
drop packets it
has no mapping for?

Distribution of     Pull       ITRs down  Push     Push    Pull
database to         CAR-CDR    load DB &  slow     fast    DNS-like
networks with       global     updates    via      Repli-  global
ITRs etc.?          network    via HTTP   BGP      cator   network
                               from DB             system
                               servers &
                               other ITRs

Incremental                    RRG                 Yes
deployment via                 messages

* Perhaps CONS might be changed to incorporate full DB ITRs to
  which packets would be sent when the caching ITR has no
  mapping information.  See
  http://psg.com/lists/rrg/2007/msg00464.html where Scott Brim,
  co-author of the LISP-CONS ID, wrote: "default mapper :-)".

See my previous message about TRRP having a push system for mapping
changes.

I wrote that only eFIT-APT and Ivip did not drop packets, but this
is true of LISP-NERD too, since all the ITRs have a copy of the full
 database.

In one sense NERD is a "push" model, since the ITRs get all the
mapping data sent to them.  In another sense, it is a "pull" model,
because the updates (and the initial body of mapping data) are only
sent when the ITR requests it.

So mapping data is only as up-to-date according to how recently the
ITR requested and received the latest update, and according to the
timeliness of those updates with respect to when the customer
signalled to the Authority their changed mapping information.

Thanks for your reply, which helped me understand your vision for LISP.

It is difficult to know what number of mappings and what volume of
changes to aim for when devising an ITR-ETR system.

With Ivip I am aiming for something with potentially hundreds of
millions of end-users, mapping single IP addresses or arbitrary
length ranges of them (not just powers of 2).  I am aiming to
support mobility, which means pushing changed mapping as fast as
possible globally.  Ivip's ITRs and mapping data is simpler than
those of the other proposals, because the ITRs make no decisions
about multihoming service restoration - so there is only a single
ETR address for every destination address.  There could be separate,
parallel, Ivip systems with some ITRs handling lots of database
changes for mapping mobile hosts/networks and others for address
space used for more traditional, non-mobile, multihoming and address
portability.

You wrote:

> At least initially, there should be no reason to cache ANYTHING.
> We simply are not yet at an inflection point where we need to.
> This is what the data will show.  If I were a betting man, I might
> put money down on us not needing a cache mechanism for many many
> years.  All of this presumes, of course, that you're updating a
> database about once an hour.  You could break it up in
> provisioning period, with time to sign and process and all.
> Hence, off-host caching is not an issue with NERD in this case.

So there may be multiple EID Database Authorities and the ITRs need
to request the latest update file, which becomes available about
once an hour.

> Now, suppose I lose my bet.

LISP-NERD is implemented and becomes a great success.  However the
volume of updates and/or the speed with which end-users want their
mapping changes conveyed to the ITRs makes the HTTP-based
ITR-initiated update-file download system impractical.

> Then I would implement CONS or something like it, and bifurcate
> the NERD database into regions, and use LISP for things that are
> outside my region.

I guess you mean full DB download NERD for ranges of addresses which
are most likely to be needed by this ITR, and CONS to request and
cache mapping information for address ranges which are less likely
to be required.

> There is some configuration complexity with this approach that I
> have not fully explored, like how do you decide what region you're
> in, and which databases to use NERD for and to use CONS for.  I
> suspect the answer to these questions lie in having a
> meta-database that is retrieved, but I've not gone much further.

Noel Chiappa discusses regions in another message, to which I will
reply.

Hello Sheng,

Thanks for your response, in which you wrote:

> Well, there may be other branch that seems been forgotten by all
> of us: the future internet architecture, of course, needs a NEW
> mapping system. An efficient, robust mapping system can reduce the
> cache issues a lot, maybe into an acceptable scope.

This means pushing mapping data either to all ITRs (no caching at
all) or at least to some ITRs and/or Query Servers which are located
in many, most or all ISP networks, and so provide much faster and
more reliable responses to queries than is possible with LISP-CONS'
global CAR-CDR network or with TRRP's global DNS-like network.

eFIT-APT proposes doing this, via BGP, which is very slow indeed.  I
am not convinced that BGP consents to this.  Most ITRs are caching
ITRs but the Default Mapper is both a full DB ITR and a query server
for its nearby caching ITRs.

Ivip does this with two types of caching ITR, two types of Query
Server (caching and full DB) and with full DB ITRs.  These can be
deployed much more flexibly than with eFIT-APT.  A minimal system
consists of a single ITRD.  I intend Ivip's database distribution
system to be very fast - a few seconds at most, globally.  This
requires a purpose-built distribution system with high reliability,
and robust security.  I am making progress on this and will write it
up as soon as I can.

> DNS-style mapping system is more than 20 years old and was mainly
> designed for the fixed network. It cannot meet the new
> requirements. If the future internet architecture was established
> on such out-of-time technology, the dead end could be expected.
>
> A new mapping system should at least support: fast updating,
> synchronization if distributed,

I am not sure what this means.

> real-time handover,

There's no way that a global distribution system will work fast
enough for voice continuity when a cell-phone physically connects to
one cell or another, or to one cell in one IP access network from a
cell in another IP access network.  Even if it did, it would be
extremely costly to transmit 12 bytes or so of changed mapping
information to a hundred thousand or more full DB ITRs and Query
Servers every time a lone cell-phone moves a few metres, or its
radio propagation conditions change.

I think that it may be feasible for a mobile device - a cell-phone
or more generally some other device - to establish two connections,
via simultaneous 3G, fibre, WiFi etc. means, and then to use the
global network to have the mapping of its public IP address changed
to the ETR for whichever link it prefers to use.  Still, the cost to
the global mapping distribution network of sending that information
to all full DB ITRs etc. all round the world is high, and I think
there needs to be a charging system per mapping change.  It probably
doesn't need to be a very high charge to make some or all of the
global system financially viable.

> choosing between multiple items, etc.

I don't understand this.

> Furthermore, it must have a business model that supports it. One
> more consideration is that it might support different ID/locator
> separate proposals if we designed it carefully.

I am designing the database distribution (Replicator) system for
Ivip alone, starting with IPv4.  Then I plan to extend it to IPv6.

Anyone who wants to use it or parts of it for any other purpose will
be welcome to do so, but I will be designing only for Ivip.  I think
that if you attempt something as difficult as this with too
demanding, and/or too vague and broad, a set of requirements, the
development time will be too long and/or the result will be bloated
and inelegant.

  - Robin

---

From: "William Herrin" <[email-masked]>
Date: Sat, 20 Oct 2007 09:12:39 -0600

On 10/18/07, Robin Whittle <[email-masked]> wrote

Hi Robin,

I'm unclear what you mean here. Would you clarify?

> Caching ITR must    Yes                   No       No      Yes

Actually, the ITR for TRRP is not required to drop packets for which
it has no map. It may drop packets if memory is tight or the mapping
occurs too slowly, but should attempt to hold them for transmission on
receiving a mapping. Specific strategies for determining which packets
to hold and for how long are not proposed.

> "anycast ITRs in               264 & 288

The answer for TRRP is Yes as well. Note the first sentence of phase 3
at http://bill.herrin.us/network/trrp-implementation.html which
explicitly envisions this step.

Regards,
Bill Herrin

-- 
William D. Herrin                  [email-masked]  [email-masked]
3005 Crane Dr.                        Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004

---

From: Robin Whittle <[email-masked]>
Date: Sun, 21 Oct 2007 13:29:36 +1000

There is an updated version of the comparison chart at the end of
this message.

Hi Bill,

I am keen for you and proponents of LISP-CONS to critique my example
of dropped (or excessively delayed) packets and sending host time-outs:

  http://psg.com/lists/rrg/2007/msg00462.html

Can anyone provide typical first and second attempt time-out values
for host code which sends UDP packets to nameservers?  Likewise,
what are typical first time-out values for establishing a TCP session?

Delaying the packet until a mapping response arrives will be better
than dropping the packet if the mapping arrives early enough that
the tunneled packet will generate a response which arrives at the
original sending host before that sending host times out.  This will
still delay the establishment of communications compared to
LISP-NERD, eFIT-APT and Ivip, but not as much as would dropping the
packet.

People in the USA and I guess Western Europe may be used to pretty
fast DNS lookups in general for the sites they most commonly
communicate with, but that is not the case for folks in the colonies
like Australia or New Zealand who often access servers in the USA
and Europe.  Does anyone have subjective impressions of this?  Many
people on this list travel to far-flung places.

Thanks for clarifying my understanding of TRRP - reminding me of
something I did understand but did not recall when I wrote this chart.

> explicitly envisions this step.

That sentence is:

  Carrot: ISPs notice that by implementing a local ITR they get
  better connectivity with servers hosted on the Micronets.

I think the most relevant sentence is in Phase 2:

  ARIN contracts one ISP to provide a route-of-last-resort for the
  the entire group of Micronets which leads to an ITR.

This form of the sentence is somewhat ambiguous, because one parsing
of it is that "the entire group of Micronets which leads to an ITR"
involves a description of this entire group leading to an ITR.  A
better form of the sentence, according to my understanding, is:

  ARIN (and likewise other RIRs, separately or together) contracts
  one ISP to provide a route-of-last-resort for the the entire group
  of Micronets.  The ISP provides an ITR which advertises the BGP
  prefixes from which the Micronets are allocated.

But this still involves "an ITR", which is not anycast.  I am not
sure if you are saying that your proposal provides for "incremental
deployment", or "incremental deployment via anycast ITRs in the
core", so I have separated the two concepts in the chart.

In theory, I can imagine incremental deployment via a single ITR to
handle one or more prefixes which are split up by the ITR-ETR
system, but I think this would involve bottlenecks and overly long
paths often enough that it would soon be decided to create multiple
such ITRs, making it "anycast" as I have somewhat redefined the term
in Ivip.

If you want your proposal to be explicit about anycast, perhaps you
could change the last sentence and add some more sentences such as:

  The ISP provides multiple ITR which advertise the BGP prefixes
  from which the Micronets are allocated.  Each ITR tunnels
  packets which arrive from non-upgraded networks to the correct
  ETR.  While each ITR has a different IP address, this arrangement
  of multiple BGP routers advertising the same prefix and
  independently tunneling the packets to their destinations has
  recently become known as "anycast ITRs in the core".  This is
  anycast routers with the same BGP advertisement, and with a single
  destination host (reachable via one or more ETRs) for each address
  or smaller subnet of addresses which the ITR maps.  The original
  RFC 1546 use of "anycast", involves multiple geographically
  separate hosts with the same IP address, each with a separate BGP
  router which advertises the same prefix which contains this
  address.

But then your proposal will lose its terseness and start to resemble
a fulsome Ivip document!

Below is an updated version of the comparison chart.

  - Robin

Caching ITRs?       All*       No**       ITR      ITRC    All
                                                   ITFH

Caching ITR drops   Drop                  No -     No -    Delay
packets it no                             sends    goes to
mapping for or                            to       >=0
delays them until                         Default  ITRCs
mapping arrives?                          Mapper   then
                                                   ITR

Incremental                    Maybe:              Yes:     Yes:
deployment via                 Anycast             Anycast  Anycast?
one or more                    RRG mssg            ITRs     RRG mssg
(>1 = "anycast")               264 & 288           in the   484 ...
ITRs in the core?                                  core

*   Perhaps CONS might be changed to incorporate full DB ITRs to
    which packets would be sent when the caching ITR has no
    mapping information.  See
    http://psg.com/lists/rrg/2007/msg00464.html where Scott Brim,
    co-author of the LISP-CONS ID, wrote: "default mapper :-)".
    See also Dino's message 476 and following discussion 481 & 482
    regarding Re-Encapsulating Tunnel Routers as "default mappers".
    I suggested using these as local query servers.

**  See RRG mssg 471 regarding LISP-NERD using CONS in the future if
    it can't scale well for larger databases and/or more frequent
    mapping updates - perhaps with some "regions" of EIDs being
    handled quickly by NERD and others by CONS.

TRRP also has a method by which some ITRs (depending on how directly
they queried the authoritative DNS-like mapping information servers)
get push notification of changed mapping from the authoritative
mapping servers.  However I think this would not would scale well.

LISP-NERD, eFIT-APT, Ivip are the only proposals in which all
packets are tunneled without delay.  The original form of LISP-NERD
does it directly from the ITR, so path-lengths are always optimal -
but this is only for packets sent from sites which have been
upgraded.  Messages 264 & 288 concern more distant ITRs, not unlike
Ivip's, to maintain connectivity from non-upgraded networks.  With
Ivip, all packets find an ITR and so are tunneled immediately, but
the ITR may be far away (depending on where the nearest "anycast ITR
in the core" is), so the path may be sub-optimal.  Every eFIT-APT
network has one or more default mappers (each is a full database ITR
and query server), which always tunnels packets, generally on
optimal paths - but there is currently no provision, AFAIK, for
tunneling packets sent by hosts in non-upgraded networks.  (See RRG
mssgs 446 & 455.)

---

From: "William Herrin" <[email-masked]>
Date: Sun, 21 Oct 2007 16:42:36 -0400

On 10/20/07, Robin Whittle <[email-masked]> wrote:
> original sending host before that sending host times out.

Hi Robin,

This is purely a SWAG (it needs careful testing in operation) but my
suspicion is that the 80th percentile TRRP map lookup via DNS will
come in under 200ms. This is because the bulk of the heirarchy will
tend to stick around in the resolver's cache so that the resolver will
already know within a step or two who to ask for the authoritative
map. The map needs a fast timeout but the heirarchy can have a TTL
measured in days.

200ms is a dialup's round trip. For the first packet only. You and I
might notice the extra bump on our SSH connect time if we're paying
attention but Joe Shmoe surfing the web won't.

Anyway, this is clearly an open issue with TRRP that needs to be
addressed with real data rather than educated guesswork.

And as you point out, there may be regional differences in DNS
response time that have to be ironed out. Fortunately this issue has
been addressed before with DNS: the answer is to distribute key
portions of the heirarchy via anycast DNS servers to reduce the cost
of a cache miss. This is currently being deployed for the root zone
and its not outside of expectations for it to be deployed for the
major TLD's as well.

This, by the way, is one advantage of overloading route mapping
operations on an existing distributed map service like DNS: we don't
have to reinvent the wheel. For almost any problem we can think of,
the scalability issues have already been addressed.

> [...]

Any deployment (anycast or otherwise) starts with one machine, adds a
second and builds from there.

In the TRRP implementation timeline I tried to envision who these
folks are, why they would deploy an ITR and what scope the ITR would
have. In this context, I think "why?" means "what immediate economic
advantage is derived from the deployment?"

For the first ITR, I create a supply which addresses a previously
unmet demand: micronets. As things stand today, you can't get provider
independent (PI) space unless you can justify a /22. That means
hundreds of Internet-facing machines which eliminates SOHOs and small
businesses from the running. Even if you have a legacy /24, its costly
to get it routed.

So, I create micronets. These are /25 to /29 PI prefixes which can
never be routed in the DFZ. They are only reachable via TRRP.

For these micronets to be reachable by networks without an ITR,
someone has to deploy an ITR and announce a covering "route of last
resort" which leads to an ITR. So, we put it out for bid and one
company wins.

Why would any company bid? Because its almost free money. Until ITRs
are ubiquitously deployed, that company will essentially have a
monopoly on PI micronets.If you want any real inbound bandwidth for
your micronet then until TRRP is ubiquitous, you'll have to pay them.

So, they deploy the first ITR. Global scope limited to the covering
prefix for the micronets.

Who's next? Who deploys the second ITR where the process becomes anycast?

My bet is that it will be the CDNs like Akamai and the route
optimizers like Internap. For one thing, the CDNs make their money by
optimizing delivery. Implementing a local ITR optimizes delivery to
the micronets. For another, they have the technology and are well
positioned to vend optimizing DNS route servers to the micronet
customers. Its a new product line they're uniquely positioned to
offer. Will they jump on the opportunity? You bet they will.

So the CDNs deploy local scope ITRs which take priority over that
first ITR for the Micronets prefix(s). But they also dump the local
default route into the ITR. They read the documentation on TRRP.
That's what it said to do and they lose nothing by doing so.

Who's next? How about peering managers? If your traffic is heavy
outbound and you need to improve your ratio or be depeered, dragging
in the traffic for TRRP can't hurt. Scope: regional default route.

Next? By now micronets are a big enough deal that niche ISPs can
benefit. Deploy an ITR, ETR and DNS route server. Help the customer
get a micronet assignment. Presto: new product. How long has it been
since niche ISPs have had a genuinely new product with which to
freshen their advertising?  Scope: local default route.

Next? None of this is happening in a vacuum. Time marches on and we
close in on IANA free pool exhaustion. IPv6 deployment remains way
behind the curve so the feared address market develops and the DFZ
route table starts to explode. All the backbones will have a bad
couple quarters as they deal with a forklift upgrade cycle.

But not all backbones are created equal: some sell bandwidth cheap on
a razor thin margin. You know who I'm talking about. Those guys won't
have a bad quarter; they'll have a crisis.

Fortunately, a solution presents itself. A dozen TRRP ITRs can be had
for less than the cost of the smallest core router. So, they deploy
ITRs and announce a default (and the Micronet covering prefixes) to
their customers. Then its 60 days notice: Razorthin will discontinue
BGP routing for non-customer /24''s. To retain connectivity, announce
a covering route or establish an ETR.

They will take a hit for this. Even being careful not to exclude
things like the /24 for f-root they'll have a few weeks in which
worldwide connectivity is not complete before everybody gets the
message and deploys an ETR. They'll lose some customers too. But
they'll have avoided a crisis that would have cost tens of millions of
dollars that they didn't have. And the net result is that just about
everybody in the world with a PI /24 will now have a TRRP ETR. Scope:
national default route.

What then? Well, the other backbones like saving money too. Once
Razorthin has taken the hit and caused ETRs to be deployed, they'll
deploy ITRs and reduce their routing tables as well. Scope: global
support of TRRP.

Deployment of ITRs and ETRs continues, of course, but its purpose is
optimization. At this point, TRRP is globally deployed and (knock on
wood) working. At each step along the way here, each organization
which deployed a TRRP component had an immediate economic advantage
for doing so.

> core", so I have separated the two concepts in the chart.

In the sense of ITRs having the same IP address, none of the proposals
are anycast, are they? The ETRs could be anycast but why would you
make the ITRs anycast? Perhaps I misunderstand?

In the sense of multiple distributed ITRs originating the same
prefixes and being able to properly handle any address within the
prefixes, TRRP is anycast.

>   [...]

Ha! That's why I put it in hyperlinked web pages instead of trying to
write an internet draft straight off. I can keep the core of the
proposal reasonably concise and still expand on topics that need more
explanation.

Regards,
Bill

---

From: Robin Whittle <[email-masked]>
Date: Mon, 22 Oct 2007 15:27:02 +1000

Hi Bill,

Thanks for your response.  Even if most of the TRRP map lookups take
200ms or so, and if the ITRs hold the data packets and send them
when the mapping data arrives, the system will be slower than
LISP-NERD, eFIT-APT and Ivip.  As I understand LISP-CONS, packets
for which there are no mapping are dropped, which would be much
slower in general than TRRP holding packets to wait for mapping
data, since each attempt at establishing a TCP session will involve
multiple time-outs and retries.

What about the recursion of looking up such a depth of TRRP servers
with IPv6?  Each four bits requires a new level of nameserver.

I guess the ITR keeps drilling into this tree of nameservers until
it finds one which is authoritative for the address it is seeking
mapping for.  Assuming the TRRP-mapped address blocks (each
of which contains one or probably more micronets) are /32, this
still involves 8 levels of server recursion.  I understand the ITR
would probably have cached the addresses of the first few levels of
this, but it still involves a likely drilling into four or so
levels.  If so, then my example, showing two levels of recursion,
would be a better than average case.

If there was a single, unified, global system of anycast servers
(anycast on the same IP address), each with their nearby BGP
router advertising the one /24 in which all those servers have their
addresses, for the top level domains, then this would reduce the DNS
lookup time somewhat for far-flung hosts.  I think it would
partially solve the problem I point to in my example of each
nameserver farms relying on a caching ITR to send packets back to
the sending host.

>From Australia, New Zealand and some other countries there might be
an anycast TLD server farm in Sydney.  The TRRP ITR there would
have a better chance of caching the mapping information for sending
responses back to hosts in the region for several reasons than an
ITR of the current TLD nameservers.

Firstly.  Most (all?) of the requests the farm handles would come
from the Australia-NZ region, which involves a relatively small
subset of the total address space.  Therefore, for a given memory
capacity and/or query traffic limit, the ITR of the farm can retain
the mapping details for longer for these addresses than could an ITR
of a single global (actually a few global) TLD nameserver.

Secondly, by implementing nameservers for most or all TLDs in these
anycast farms which share the one TRRP ITR, it is much more likely
that the ITR will already have cached an Australian sending host's
mapping information when the host is sent a response for the .ru
nameserver there, because the same host would have been recently
getting responses from the .au server in the same farm.

For many lookups, this would mean there is only one level of
recursion required - to find the .xxx.com.au server, and then to ask
it the IP address(es) of www.xxx.com.au.  I guess that most DNS
lookups today involve a depth of three or four - four for
www.xxx.com.au.

I will discuss your TRRP deployment plans in a separate message.

I had never heard of SWAG.  I figure you meant Scientific Wild Assed
Guess, but there are others to choose from:

http://slang.acronymfinder.com/af-query.asp?acronym=swag&string=exact&s=r

including "Still Wondering and Guessing"!

    - Robin

---

From: "William Herrin" <[email-masked]>
Date: Mon, 22 Oct 2007 09:37:10 -0400

On 10/22/07, Robin Whittle <[email-masked]> wrote:
> LISP-NERD, eFIT-APT and Ivip.

Hi Robin,

TRRP will be slower on the first packet of the day (and the first
packet after an ITR failover) than any system based on carrying a full
table of all possible maps. The trade off is scalability: TRRP ITRs
need only hold maps for hosts actively talking to each other. This
allows it to accommodate a vastly larger total number of maps.

Imagine trying to build a DNS resolver so that every hostname in the
world was pre-cached on every resolver. Even if allowed to cache
rarely used names on disk instead of in ram, resolvers would have to
be massive and incredibly expensive. And the data flow necessary to
keep all the resolvers up to date would be astonishing.

I propose that what makes no sense for name-mapping likely makes
little sense for address mapping either.

Back at the beginning of time, we had a hosts file and we had RIP. As
we outgrew these choices, we replaced them with DNS (a pull based
mapping system) and BGP (a push based mapping system). We're talking
about replacing/supplementing BGP in what is not the first table-size
crisis while DNS chugs along happy as a clam. This says something
about the relative merits of push versus pull mapping systems. That
entry-level DNS servers cost $500 while entry-level BGP routers cost
$30,000 says even more.

> with IPv6?  Each four bits requires a new level of nameserver.

DNS is smarter than that. Each non-recursive query generates a
response with as many hierarchy components as possible. Let me
illustrate with a tcpdump of a query for the MX record for
web.listbounce.democrats.org:

07:55:52.424803 IP (tos 0x0, ttl  64, id 0, offset 0, flags [DF],
length: 85) 71.246.241.146.32825 > 199.19.56.1.53: [udp sum ok]  4637%
[1au] MX? web.listbounce.democrats.org. ar: . OPT UDPsize=2048 (57)

07:55:52.451070 IP (tos 0x0, ttl 247, id 49173, offset 0, flags [DF],
length: 153) 199.19.56.1.53 > 71.246.241.146.32825: [udp sum ok]
4637- q: MX? web.listbounce.democrats.org. 0/2/3 ns: democrats.org. NS
ns2.democrats.org., democrats.org. NS ns1.democrats.org. ar:
ns2.democrats.org. A 208.69.4.67, ns1.democrats.org. A 208.69.4.66, .
OPT UDPsize=4096 (125)

07:55:52.453286 IP (tos 0x0, ttl  64, id 0, offset 0, flags [DF],
length: 85) 71.246.241.146.32825 > 208.69.4.67.53: [udp sum ok]
40647% [1au] MX? web.listbounce.democrats.org. ar: . OPT UDPsize=2048
(57)

07:55:52.461228 IP (tos 0x0, ttl  57, id 0, offset 0, flags [DF],
length: 191) 208.69.4.67.53 > 71.246.241.146.32825: [udp sum ok]
40647*- q: MX? web.listbounce.democrats.org. 1/2/4
web.listbounce.democrats.org. MX mail1.democrats.org. 10 ns:
democrats.org. NS ns2.democrats.org., democrats.org. NS
ns1.democrats.org. ar: mail1.democrats.org. A 208.69.7.20,
ns1.democrats.org. A 208.69.4.66, ns2.democrats.org. A 208.69.4.67, .
OPT UDPsize=4096 (163)

Notice four things:

1. Each nonrecursive request included the full query, not just a
component of it.

2. Only two queries were needed to get the result for a DNS name with
four levels of hierarchy.

3. The first query went to a0.org.afilias-nst.info, one of the
authoritative name servers for .org. This is because the DNS server
already had the root zone cached and didn't need to query the root
server to find .org.

4. When the authoritative server for "democrats.org" was found, it
only had to be queried once to find web.listbounce.democrats.org
because it had all the remaining levels of hierarchy.

> getting responses from the .au server in the same farm.

If I understand what you're getting at, that's more or less correct.
TRRP may be significantly more efficient if:

1. Cache misses from the ITR's resolver are referred to a regional
resolver farm for help performing the recursive query rather than
locally implementing the non-recursive query.

2. The nameserver addresses are found with glue inside the trrp
hierarchy rather than stepping outside the hierarchy like in-addr.arpa
does.

3. The resolver (or resolver farm) emits queries from a globally
routed address instead of from a TRRP address.

There are several such situations in TRRP where operationally it will
make more sense to use a globally routed address than a TRRP address.
That's OK. TRRP is not intended to replace BGP; its intended to
drastically reduce the number of prefixes that have to be carried via
BGP.

> Guess,

Yep. :)  I could have said, "educated guess," but SWAG is more amusing.

Regards,
Bill Herrin

---

From: <[email-masked]>
Date: Tue, 23 Oct 2007 11:00:37 +0100

Bits cut 

> 
> Back at the beginning of time, we had a hosts file and we had 
> RIP. As we outgrew these choices, we replaced them with DNS 
> (a pull based mapping system) and BGP (a push based mapping 
> system). We're talking about replacing/supplementing BGP in 
> what is not the first table-size crisis while DNS chugs along 
> happy as a clam. This says something about the relative 
> merits of push versus pull mapping systems. That entry-level 
> DNS servers cost $500 while entry-level BGP routers cost 
> $30,000 says even more.
> 
 Does this really say anything about the relative merits of push versus
pull?
I rather thought DNS chugs along because it does not have to handle the
same amount of changes that BGP does? Ok, the churn problem is harder if
you try push, but people expect to be able to make route changes in
seconds, ms being talked about as a target; I rather think to change my
DNS entry takes a little longer.

Louise

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 23 Oct 2007 12:51:36 +0200

> DNS entry takes a little longer.

The problem isn't changing the entry on your server, but the delay  
caused by the caching. In a push model, the entity doing the pushing  
knows when a new push is required. In a pull model, the entities  
doing the pulling have no idea when would be a good idea to execute a  
new pull.

However, I think it would be possible to come up with a fairly light- 
weight way to push out notifications that a new pull is in order. And  
if the decapsulating devices get to see the addresses of the  
encapsulating devices, they can easily signal back that there was a  
change of some sort. Or say the same thing implicitly by becoming quiet.

---

From: [email-masked]
Date: Tue, 23 Oct 2007 13:39:37 EDT

In einer eMail vom 23.10.2007 12:53:11 Westeuropäische Normalzeit schreibt  
[email-masked]:

caused by the caching.

I can only (patiently) collect such information for argumenting (later on)  
in favor for some model which does not need caching (of what it does not need  
distributing). Also never mentioned before: A next hop determination might be  
faster in case the  FIB contains approx. 2-3 K entries only.
Heiner

---

From: "William Herrin" <[email-masked]>
Date: Tue, 23 Oct 2007 17:45:32 -0400

On 10/23/07, [email-masked] <[email-masked]> wrote:
> > We're talking about replacing/supplementing BGP in
> > merits of push versus pull mapping systems.
>

Louise,

I suppose its fair to look at the assumptions. If the assumption is
that a given map server will need to interact with most of the maps
then its pretty easy to falsify the claim. If the assumption is that a
given map server will need to interact with only a small number of
maps then the claim is fairly straightforward.

Let me ground that a bit: if we get great heirarchical aggregation
where each map covers a very large number of EIDs then push will be
more efficient. If we get heavy fragmentation and deaggregation then a
pull will be best. So, pull out your crystal ball and tell me which
assumption will hold true.

> same amount of changes that BGP does?

DNS experiences a vast amount of churn, far more than BGP. It doesn't
meaningfully impact the system overall because resolvers only care
about the changes to the records with which they're currently
interacting.

Two major sources of churn in DNS:

1. Dynamicly constructed A-records form the technological basis by
which CDNs like Akamai function. Every single query may return a
different result.
2. Orgs like dnydns.com change A records every time a single PC comes
up or goes down.

> Ok, the churn problem is harder if

That is a weakness with the basic DNS approach. Resolvers hold the old
record until the TTL expires. In a practical sense, the lower bound
for a TTL will be about 60 seconds and even that's pushing it.

TRRP posits an optional preemptive change notification to address this
weakness. http://bill.herrin.us/network/trrp-preempt.html  PCN sends a
notification packet to all recent requestors when an entry changes,
advising them that they should immediately expire the old entry. If
widely adopted (its optional after all) then sub-second changes to the
target ETR should be possible.

Regards,
Bill Herrin