Subject: [RRG] Delays inherent in TRRP's DNS-like lookup?

From: Robin Whittle <[email-masked]>
Date: Fri, 22 Feb 2008 02:19:40 +1100

Hi Bill,

In "Re: [RRG] Map-encap space for 'server' vs. 'client' end-users?",
you wrote about my critique of your TRRP proposal:

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

that it could take a long time for the ITR to perform all the
DNS-like lookups to find the authoritative server for some IP
address.  This is particularly a problem with IPv6, where each level
of DNS-like hierarchy is defined by a smaller number of bits (4, I
recall) than with IPv4 (8 bits > 3 decimal characters) and where the
length of the EID to be looked up is generally much longer.

It is one thing for the ITR seeking mapping for IPv4 "92.168.100.1"
to have to find the authoritative server for:

  1.101.168.192.v4.trrp.arpa

but it would be worse with an IPv6 address (assuming /64 granularity
and therefore a limit of 64 bits on the length of any EID):

  7.A.4.6.0.3.F.4.B.0.0.E.0.0.0.2.v6.trrp.arpa

>> TRRP has a similar delay problem, which would occur frequently
>> enough to be significant.  The ITR has to sequentially query
>> and get responses from several DNS-like servers in order to
>> find the authoritative server with the mapping information.
>> Unless you anycast those intermediate servers (which does not
>> scale well) then there will be significant delays in quite a
>> few circumstances.
>
> Few if any of which will have a more meaningful impact than a DNS
> query today. The users have spoken clearly on pull-style lookup
> delays. Given a choice between reference by name and reference by
> IP address, they have consistently favored convenience over the
> extra edge in speed.

> While none of us has collected direct data on this point, the
> circumstantial data is not the slightest bit ambiguous. According
> to users' behavior with the DNS, brief lookup delays solely at
> the front of a series of transactions are A-OK.

Sure, but if a new kind of address space involves a new kind of
delay, and you have the choice between this and the original kind of
address space which has no such delays, then it is going to be hard
to get many or most people to adopt the new kind.  As Marshall
Eubanks wrote: http://psg.com/lists/rrg/2008/msg00381.html

>> This seems to be far worse with IPv6, where each level in the
>> DNS-like hierarchy is a smaller number of bits, and there are
>> more bits in the EID address than with IPv4.
>
> There is no causative correlation whatsoever between IP address
> length and DNS lookup depth.

I the assumptions you make in your example below will not apply to
your TRRP DNS-like system.

> Lookup depth correlates with administrative subdivision which
> looks no different for IPv6 than it does for IPv4.
>
> This is a factor which is easily tunable at an operations level
> if needed to meet the system's speed requirements. The lookup
> depth is not bound to the number of elements in the name.
> t.u.v.w.x.y.z.dirtside.com only has a lookup depth of 3.
> a.b.c.d.e.f.g.h.i.j.k.l.m.n.o.p.q.r.s.t.u.v.x.y.z.dirtside.com
> and
>
0.1.2.3.4.5.6.7.8.9.a.b.c.d.e.f.g.h.i.j.k.l.m.n.o.p.q.r.s.t.u.v.x.y.z.dirtside.com
>  have the same lookup depth: 3.

> But that's not the end of the story: you almost always have the
> first stop (.com) cached, so the actual experienced lookup depth
> is rarely more than 2. Should it prove operationally desirable, a
> map-pull system can easily accommodate that degree of flatness in
> the hierarchy.

I don't know as much as I would like about DNS, but I think you are
saying that the host sends a request to the nameserver which is
authoritative for dirtside.com not just for the address of the
nameservers which are authoritative for z.dirtside.com, but asks for
the address of the whole thing "0.1 ... .y.z.dirtside.com".

I don't understand how it could know to do that, unless it would
also ask for the whole thing from a nameserver which is
authoritative for .com as well.

Assuming it does this, then in your example, assuming that the one
physical nameserver (actually two or more for redundancy) which is
authoritative for dirtside.com is also authoritative for its 36
levels of subdomain, I can see that the single long query to this
nameserver would be answered with the IP address of the whole text
name: "0.1 ... .y.z.dirtside.com".

But this is only because we assume that the same nameserver which is
authoritative for dirtside.com is also authoritative for all its
subdomains.

This certainly will not be the case with your TRRP hierachy.

The nameserver which is authoritative for:

           192.v4.trrp.arpa

is highly unlikely to be authoritative for:

       168.192.v4.trrp.arpa

In your IPv4 scheme, there could be a different authoritative
namesever for every /24, for instance:

   101.168.192.v4.trrp.arpa

That is about (224 - 2) * 256 * 256 = 14,548,992 separate /24s.

There will be millions of such nameservers and there is no way the
nameserver for:

       168.192.v4.trrp.arpa

is going to be the same one as for all its 256 subdomains.

The same principle applies with IPv6, except you have 64 bits
instead of 32 (I assume your EID granularity for IPv4 goes down to
single IP addresses) and half the number of bits per hierarchical level.

I recognise that the EID isn't necessarily 64 bits long, but some of
them would be, I assume.  Otherwise you are stuck with something
like /48 granlarity.  In this example the ITR wants the mapping for
the 128 bit IP address 2000 E00B 4F30 64A7 8901 56AC 4404 0109.
With a /64 bit limit on EID length, it takes the most significant 64
bits and creates a DNS query for:

  7.A.4.6.0.3.F.4.B.0.0.E.0.0.0.2.v6.trrp.arpa

Below I show my understanding of how TRRP works, assuming this IP
address is located in a 52 bit EID.

Let's say you had a different authoritative nameserver for each
hierarchical level, which seems a reasonable arrangement.  Maybe you
could fix it at every two levels - 8 bits - which would speed up the
DNS traversal, but would clunkify delegation by forcing each level
to handle effectively 256 sub-domains.

I will assume that the ETR has already cached the address of the
nameserver which is authoritative for the first 12 bits of address,
2000E0:

                      0.E.0.0.0.2.v6.trrp.arpa

So the first lookup is to there:

Lookup 1:
                      0.E.0.0.0.2.v6.trrp.arpa

and the result comes back:

  Here is the address of the nameserver which is authoritative
  for:

                    0.0.E.0.0.0.2.v6.trrp.arpa

The ITR sends its next query there:

Lookup 2:
                    0.0.E.0.0.0.2.v6.trrp.arpa

and gets back a similar response pointing to the next level along
the hierarchy:

                  B.0.0.E.0.0.0.2.v6.trrp.arpa

The ITR keeps playing the same game,

Lookup 3:
                4.B.0.0.E.0.0.0.2.v6.trrp.arpa

Lookup 4:
              F.4.B.0.0.E.0.0.0.2.v6.trrp.arpa

Lookup 5:
            3.F.4.B.0.0.E.0.0.0.2.v6.trrp.arpa

Lookup 6:
          0.3.F.4.B.0.0.E.0.0.0.2.v6.trrp.arpa

Lookup 7:
        6.0.3.F.4.B.0.0.E.0.0.0.2.v6.trrp.arpa

where it reaches a nameserver which knows that this part of the
address space is really part of a /52 EID:

      4.6.0.3.F.4.B.0.0.E.0.0.0.2.v6.trrp.arpa

so the answer comes back, as you describe (and I only partially
understand):

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

which somehow (one more lookup?) enables the ITR to get the mapping
information for this EID.  So now it can start tunneling packets.

All these DNS lookups could take a long time.  Also, a single lost
packet would clobber the process for a second or two.  These
authoritative nameservers could be anywhere in the world.  There's
no reason they would be close to the ITR.  You could anycast
nameservers to handle the most significant address bits (rightmost
in the text name the ITR is asking about), which would speed up that
part of the process.

Please correct any misunderstanding in what I wrote above.

  - 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: "William Herrin" <[email-masked]>
Date: Thu, 21 Feb 2008 12:35:16 -0500

On Thu, Feb 21, 2008 at 10:19 AM, Robin Whittle <[email-masked]> wrote:
>  address.

Hi Robin,

This is correct. It is this weakness in TRRP that I seek to address
with optional waypoints in the (unfinished) document at
http://bill.herrin.us/network/trrp-aapip.html

>  This is particularly a problem with IPv6, where each level

This is not correct. The lookup depth is not bound to the length or
number of elements in the lookup.

>   7.A.4.6.0.3.F.4.B.0.0.E.0.0.0.2.v6.trrp.arpa

It looks like you're a step ahead of me. I was about to suggest that
you explain your understanding of how TRRP's DNS lookup works so I
could find the error. Good.

First off, the EID lookup isn't bound by any subnet masks, so the
lookup for 2000 E00B 4F30 64A7 8901 56AC 4404 0109 is the whole
enchilada:

9.0.1.0.4.0.4.4.C.A.6.5.1.0.9.8.7.A.4.6.0.3.F.4.B.0.0.E.0.0.0.2.v6.trrp.arpa

>  hierarchical level, which seems a reasonable arrangement.

This is an error. A different authoritative nameserver for each
hierarchical level is neither a reasonable nor likely arrangement.
I'll show why below.

>  nameserver which is authoritative for the first 12 bits of address,

I concur: the first 12 bits (corresponding to the IANA allocations to
RIRs) will usually be cached. That's 0.0.2.v6.trrp.arpa BTW.
0.E.0.0.0.2.v6.trrp.arpa is 24 bits.

>  So the first lookup is to there:

No. The first lookup is for
9.0.1.0.4.0.4.4.C.A.6.5.1.0.9.8.7.A.4.6.0.3.F.4.B.0.0.E.0.0.0.2.v6.trrp.arpa,
sent to one of the servers which is authoritative for
0.0.2.v6.trrp.arpa. That server will be an RIR's server. Since the
address space will be PI assigned by that RIR, this lookup will
resolve to the /48 level, matching the address assignment they made.

>  and the result comes back:

0 "answers" but multiple "authority" records for the DNS servers which
know about the heirarchy under 0.3.F.4.B.0.0.E.0.0.0.2.v6.trrp.arpa
and "additional" records which provide the IP addresses of those DNS
servers. **

Each DNS response has four sections:

1. Questions. This is the lookup that was performed.
2. Answers. The final result of the lookup.
3. Authority. The servers which know the next step in the chain and
what that step is (final answer or something before it)
3. Additional: Information that you'd otherwise likely ask for, if it
happens to be known to the server. An "Additional" section for most
lookups will try to contain the A and AAAA records that match the NS
records in the authority section.

>         6.0.3.F.4.B.0.0.E.0.0.0.2.v6.trrp.arpa

No. Lookup #2 is also for
9.0.1.0.4.0.3.3.1.0.9.8.7.A.4.6.0.3.F.4.B.0.0.E.0.0.0.2.v6.trrp.arpa,
but it is sent to one of the servers which are authoritative for
0.3.F.4.B.0.0.E.0.0.0.2.v6.trrp.arpa.

The server for 0.3.F.4.B.0.0.E.0.0.0.2.v6.trrp.arpa is inside the
administrative domain for the end-user who controls that /48. If he's
a particularly large end user, he might delegate pieces of it. Usually
though, this second query will produce an authoritative answer.

9.0.1.0.4.0.3.3.1.0.9.8.7.A.4.6.0.3.F.4.B.0.0.E.0.0.0.2.v6.trrp.arpa
IN TXT "80,g6,2000:1234::1"

Which says: encapsulate packets for this destination in IPv6 GRE
tunnel packets and send those packets to 2000:1234::1.

** There is a hitch with the "additional" section that comes back from
the first query. If you've named the DNS server directly under the
TRRP hierarchy then the response will also include "additional"
records which give the A or AAAA records that match the names in the
NS "authority" records. If you've followed normal practice for
in-addr.arpa server naming then those "additional" records won't be
available. Instead, you'll have to pursue another lookup tree to map
the NS server names to IP addresses.

At an operations best-practice level, I expect that the relevant DNS
server names -will- be placed in the TRRP hierarchy so that the next
DNS server's IP address always comes back as an "additional" record.
TRRP doesn't require this but it makes operational sense.

>   http://bill.herrin.us/network/trrp-nm.html

This is for situations where a machine will communicate with multiple
nearby addresses. For example, lets say that you're Google and all 253
IP addresses from 199.33.224.2 through 199.33.224.254 will communicate
with you.

When you see a packet for 199.33.224.2, you'll look up
"2.224.33.199.v4.trrp.arpa" and get "80,g4,198.4.5.227 ff,nm,24".

When you see a packet for 199.33.224.3, you'll look up
"3.224.33.199.v4.trrp.arpa" but at the same time you'll also look up
"24.224.nm.33.199.v4.trrp.arpa." because of the ff,nm,24 entry you got
with the lookup for 199.33.224.2. The answer to the second query will
be "80,g4,198.4.5.227". That's your netmask entry and it means that
198.4.5.227 is a valid IPv4 GRE ETR for all of 199.33.224.0/24.

When you see a packet for 199.33.224.4, you'll send it immediately to
198.4.5.227 because you'll already have cached the netmask entry for
"24.224.nm.33.199.v4.trrp.arpa.". You won't have to look up
"4.224.33.199.v4.trrp.arpa" at all because you already have the
answer.

>  Eubanks wrote: http://psg.com/lists/rrg/2008/msg00381.html

Marshall wrote, 'the delays cannot be "significant," which [Marshall]
would regard as meaning "being noticeably larger than typical DNS
delays."'

The delay in TRRP is not noticeably larger than a typical DNS delay.
In fact, it is precisely a typical DNS delay.

>  the address of the whole thing "0.1 ... .y.z.dirtside.com".

Yes, that's exactly what the DNS resolver does.

>  authoritative for .com as well.

That's exactly what the DNS resolver does.

>  That is about (224 - 2) * 256 * 256 = 14,548,992 separate /24s.

Certainly. But the probability is that the nameserver for
192.v4.trrp.arpa knows all 65536 nameservers for the /24's under it.

Because the typical case takes exactly two non-recursive lookups
(given 256 already-cached top levels) to get all the way to the /32
even though you're potentially talking about 14M nameservers from
which to choose, TRRP scales wonderfully.

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: Sat, 23 Feb 2008 01:56:26 +1100

Hi Bill,

Thanks for explaining TRRP in greater detail and improving my
understanding of DNS.  I will return to that below.

>>  delay, and you have the choice between this and the original
>>  kind of address space which has no such delays, then it is
>>  going to be hard to get many or most people to adopt the new
>>  kind.  As Marshall Eubanks wrote:
>>
>>     http://psg.com/lists/rrg/2008/msg00381.html
>
> Marshall wrote, 'the delays cannot be "significant," which
> [Marshall] would regard as meaning "being noticeably larger than
> typical DNS delays."'

I guess typical DNS delays for hosts in the USA for US-based
nameservers are probably well under 100msec.

What matters is not so much whether the actual delay is experienced
as significant by the client users of the servers of the end-users
who are considering map-encap space.  The real question is whether
the delays inherent in an ALT or TRRP based system are enough for at
least some marketing folks to trump it up to the broader end-user
population as being significant.

Even if the difference is believed by end-users to be minor, it is a
reason to avoid this kind of address space.  So I think we need to
keep delays really, really short, under all circumstances.  As far
as I can see, that precludes the reliance on global networks of any
kind for retrieving mapping or for delivering packets while waiting
for mapping to arrive.

Even if the global network was pretty optimal, it would add delay in
many instances - especially if you are out in the Colonies here in
Australia.  There is a 287ms round trip time from Melbourne to
Dallas TX, for instance.

ALT paths are likely to be much longer than optimal.

Looking at your IPv4 example, I understand the following would happen.

The ITR is looking up mapping for:

   111.22.33.44

so it sends a query about:

   44.33.22.111.v4.trrp.arpa

to one of the authoritative servers for:

            111.v4.trrp.arpa

- which it can do instantly, since it has already cached all such
authoritative servers xxx.v4.trrp.arpa.

So that is 8 of the 32 bits taken care of already.

In this example, this nameserver is run by an RIR and it knows about
65536 sub-domains - another 16 bits chewed through in one
request-response.  The answer comes back in the form:

  You should ask the server (IP addresses supplied) which is
  authoritative for:

      33.22.111.v4.trrp.arpa

The ITR now sends the same query to this server, and gets an
authoritative response with the mapping information it needs.

So for IPv4, you think the RIR's server would do this task of
handling up to 2^16 subdomains.  That sounds technically feasible,
but would the RIR really want to do this?

This would require administrative control of some aspect of the
RIR's server from a very large number of end-user organisations.

Wouldn't it be more likely that the RIR gave a /12 of this /8 to
some ISP, and would simply hand back an answer saying to ask the
nameserver of that ISP?  Then that server might delegate to another
one, which is authoritative.

I think your approach to reducing the delay time in finding the
mapping information depends very much on collapsing what would
normally be a multi-level delegation arrangement into a much flatter
model, which might be at odds with actual business relationships.

Another critique is that this RIR server is going to be very busy
indeed.  You could anycast these /8 level servers, but that would be
costly and harder to administer, since they all have to know so much
about the authoritative nameservers for up to 64k subdomains.

Broadly speaking, if there are about 220 /8s in use in IPv4, then
each such RIR server (really multiple servers) is going to get 1/220
of the total global ITR initial requests for mapping information.

This would not be the case if each such RIR nameserver only gave
answers which solved another 4 bits (for instance) of the ITR's
problem.  Then, many ITRs would have cached the locations of the
authoritative nameservers for some or many of these 16 subdomains.
That would greatly reduce the load on the /8 RIR server.

So I think your attempt to have the RIR server know about so many
subdomains dooms it to be asked far more often than would otherwise
be the case.  This creates a global performance bottleneck, in this
case, a separate one for each /8.

looking at your IPv6 example in the same light, the figures are more
extreme.

Your first asked server is authoritative for a whopping /12 of IPv6
space.  It gives an answer about what server to ask, solving another
 36 bits of the ITR's problem:  it tells the ITR the address of
another server to ask, which is authoritative for a /48.

Do you expect this /12 server to know about (a theoretical maximum)
of 2^36 subdomains?  That is an awful lot.

Again, this server is going to be hit for a large proportion of IPv6
initial mapping enquiries, because it doesn't delegate to other
servers which themselves cover a substantial fraction of its space -
such as 16 servers for /16 prefixes.   These would tend to be cached
by ITRs and most subsequent queries would go to them, rather than to
the /12 server.

In your example the /48 server knows enough about its subdomains to
give the full answer - right down to 112 bits.  That is a huge jump-
but I guess we can assume that the huge space this involves will be
only sparsely populated by actually used addresses, and therefore
sub-domains.

Overall, I question how your collapsing of what would otherwise be a
long series of lookups into two or three will be problematic in
terms of:

1 - The business and therefore trust relationships probably
    go in steps of fewer bits than the large jumps in bits
    you use in the examples - raising questions of how the
    short-prefix nameservers get to be reliably configured with
    so much detailed information which is actually controlled
    by so many ISPs or end-users.

2 - How this collapsing thwarts the ITR's ability to cache
    a larger number of nameservers which will actually be
    used in subsequent requests - thereby requiring it to
    keep asking the /8 (IPv4) or /12 (IPv6) servers time
    and again.  The same goes for the world's ITRs and so
    these servers get a hammering.

  - Robin

---

From: "William Herrin" <[email-masked]>
Date: Fri, 22 Feb 2008 12:42:56 -0500

Hi Robin,

That is how things are constructed for the in-addr.arpa domain. Most
allocations are longer than /16, so the corresponding delegations
happen as /24's. It works in practice, today.

The scaleups necessary for the roots and tlds would probably be
necessary for the /8 level of the TRRP hierarchy, but those are also
well tested.

>  one, which is authoritative.

Not if it harms performance. At one point the first letter of .com
domains was reserved against the possibility that they'd need to do
that sort of delegation but the operators chose anycast instead.

>  of 2^36 subdomains?  That is an awful lot.

That is essentially how the ip6.arpa hierarchy for reverse-DNS is
organized today. No problems are experienced or forecast.

>     by so many ISPs or end-users.

In a PI world, the administrative relationships -are- relatively flat:

IANA-RIR-Org-Individual and IANA-RIR-Individual

It's only in the PA world we're trying to eliminate that the
administrative relationships get deep:

IANA-RIR-LIR-LIR-LIR-Org-Individual

>     these servers get a hammering.

The worst case of this problem is precisely the dot-com zone problem
which is already solved and deployed at an operations level.

> The real question is whether

Of course they are. And if it's not the milliseconds it'll be the
bytes. You have to transmit more bytes with map-encap so it'll cost
you more.

The marketing game is to make sure that at least some people see the
advantage of selling the new capabilities. "With map-encap, we can
sell you PI for $20/month. That loser who says map-encap is crap won't
sell you PI for less than $2000. Two-kay. Twenty bucks. You tell me
who's full of crap."

Regards,
Bill Herrin

---

From: Robin Whittle <[email-masked]>
Date: Sun, 24 Feb 2008 14:33:24 +1100

Short version:  How TRRP's DNS system could be souped up to
                provide much faster response times.

                This involves integrating the nameservers and
                anycasting them all from multiple sites around the
                Net.  The result is a hybrid push-pull query server
                network.

Hi Bill,

You wrote:

>> handling up to 2^16 subdomains.  That sounds technically
>> feasible, but would the RIR really want to do this?
> 
> That is how things are constructed for the in-addr.arpa domain.
> Most allocations are longer than /16, so the corresponding
> delegations happen as /24's. It works in practice, today.
> 
> necessary for the /8 level of the TRRP hierarchy, but those are
> also well tested.

OK, based on other things you wrote, I understand that each
nameserver which is authoritative for a /8 subdomain
xxx.v4.trrp.arpa will have a bunch of anycast nameservers which are
authoritative for about 64k /24 subdomains.

This means a typical IPv4 TRRP mapping lookup involves a query to
one of the /8 nameservers followed by a query to the nameserver
(presumably not anycast) which is authoritative for the /24 in which
the destination IP address lies.

Anycasting these /8 nameservers, say to 18 different locations (my
guess for the purpose of discussion) means you are spreading the
first lookup load over about 220 conceptually different nameservers
(according to the need to look up addresses in each /8, which will
vary according to traffic sent to each /8) - so this is not the same
as evenly spreading the whole load over 220 nameservers.

(220 is a guesstimate of the /8s 0 to 223, minus 10, 127 and
probably a few others which won't be used for public unicast space.)

Then, assuming the anycasting is done in a consistent, efficient,
regularised approach you have 18 sites around the world which
anycast all 220 nameservers.  This spreads the load further,
reducing the load per nameserver by very approximately a factor of
18, depending on the locations of the 18 sites.

You could have each nameserver, for instance the one (actually you
would have at least two nameservers on two addresses in at least two
different locations) which is authoritative for the prefix
123.0.0.0/8, that is the one authoritative for the domain:

  123.v4.trrp.arpa

exist in various locations and addresses.  The diversity is in three
dimensions.

Dimension 1: One of two IP addresses.

The system starts with the domain v4.trrp.arpa specifying two IP
addresses for two physically different and geographically separate
nameservers:

   11.22.33.44   For instance in New York.
   55.66.77.88   For instance in Tokyo.

Dimension 2: 18 anycast sites for each of these.

Then, assuming you want to anycast these to 18 sites, you need a
total of 36 sites around the world.

There's not much point in having a single site which anycasts both
addresses, because if that site died the whole catchment area for
that anycast site would have no nameserver for this domain.

So you pick 18 sites scattered around the world for each IP address.
 For instance:

   11.22.33.44    Sydney, Bangkok, Tokyo, Beijing, Kolkata,
                  Saint Petersburg, Istanbul, Cairo, Warsaw,
                  Berlin, Stockholm, Edinburgh, Milan,
                  Sao Paulo, Montreal, Chicago, San Francisco,
                  Hawaii.

   55.66.77.88    Melbourne, Singapore, Singapore, Hong Kong,
                  Mumbai, Moscow, Jerusalem, Cape Town, Athens,
                  Rome, Paris, London, Madrid, Buenos Aires,
                  New York, Dallas, Los Angeles, Auckland.

Dimension 3: The load is spread over 220 servers, rather than
having the queries go to a server which is authoritative for
v4.trrp.arpa.

So while this is a global query server system, the average path
length to the nearest anycast nameserver will be some smallish
fraction the radius of the Earth.

This is definitely faster than a global query server system with a
single server "somewhere" - 0 to half the circumference of the Earth
(or worse, due to paths not being directly in a half-circle to the
server).  Even this single global server approach, via ordinary
Internet links, would be faster than a single server somewhere, with
a circuitous set of hops between routers, as with ALT, which makes
the total path length typically much longer still.

So far, all this has done is increase the robustness and decrease
the time delay for the first query.  So far, so good.

In order to anycast the servers like this, you are probably going to
form a consortium to do the whole thing in an orderly fashion.
Though I suppose you could have one consortium for one set of
servers (of which 11.22.33.44 is in the A set, and 55.66.77.88 the B
set).  Then Consortium A sets up 18 sites and Consortium B sets up
the other 18, in generally different locations.

This pooling of resources makes the anycast system less expensive
than if the RIR which runs 111.0.0.0/8 and a bunch of other /8s has
to build its own set of anycast sites, while other RIRs etc. need to
do the same independently.

The second query is probably going to be to a single server
somewhere, or to one server chosen at random from a short list, with
them being geographically dispersed for robustness.  The path to the
chosen server is typically between 0 and about half the
circumference of the Earth.

Operators of /24s which have a lot of traffic could choose to
anycast their .trrp.arpa nameservers, so that on average there is
only a relatively short path to nearest one - but that could turn
into an awful lot of nameservers.  Unless those anycast servers for
the addresses which are run by many different operators were
consolidated into some smaller set, they would chew up quite a lot
of /24s to anycast them, as well as being expensive to run since
they are so numerous.

Maybe there is some snappy way you could have both kinds of
nameserver anycast, with relatively few physical servers to handle
the entire job.  Then, to the extent that you anycast them both, you
are both spreading the load and reducing typical paths for the two
queries and the two responses.

This turns what began as a global query server system into a bunch
of servers which are more local to each ITR.

One advantage of this is that you can start small, with a pair of
ordinary nameservers, and without changing the protocol or the ITRs
scale the system up to handle very large numbers of queries, with
shorter response times and greater reliability.

With a hundred or so sites around the Net, the great majority of
ITRs would be geographically close, such as a few percent of an
Earth radius - with the more remote ones still being close enough
that the delay is greatly reduced.

But then, you have just created a hybrid push-pull system of sorts,
since you need to push mapping information out to each of the 100
anycast server sites!

If you are doing this slowly, you could probably use rsync.

If you could maintain the pattern of ITRs caching the addresses of
the servers authoritative for 220 or so /8s, and then have the ITRs
doing a query and getting a response, then making another query and
getting a response, then provided you weren't troubled by packet
losses and the servers always responded, you would have a pretty
fast, generally "local" query server system.

But what if some large ISP wanted its own set of anycast servers?
They may prefer to get an rsync feed and run their own anycast
servers, to improve the response time of their ITRs (and so gain a
marketing advantage).  For instance, some USA-based ISP wants to put
a pair of anycast sites, just like those described above, in Houston
and Atlanta.   They are happy to pay for the servers - so this
reduces load on the main system.

Pretty soon, there could be many more anycast sites, especially as
each one is taking less load than the 36 big sites, and so can
probably be implemented in a smaller number of servers.  Next, the
USA-based ISP decides to put a pair of nameservers in each of their
data centres, one for each set of IP addresses for each of the pairs
of servers for each xxx.v4.trrp.arpa domains.  They use their
original rsync feed and fan this data out to their multiple sites.

Now, you can't very well alter the IP addresses of the nameservers,
because multiple ISPs such as this would have the disruptive task of
changing their many sites to new addresses.   So, initially,
ideally, before things got to this stage, you would probably want to
choose IP addresses for the various xxx.v4.trrp.arpa sites so that
they all fitted nicely into a single /24, which could be anycast
with less fuss than a bunch of /24s.  This would be further pressure
for the initial deployment of nameservers to be done by a
consortium, rather than completely independently by multiple RIRs etc.

The RIRs or that consortium would need to charge the end-users whose
address space was in these /8s, because some of that address space
will generate very few queries and some will generate a lot.  So
there would be enquiry traffic based billing for running these
anycast nameservers.  A low-key outfit with a lightly used /16
wouldn't want to be paying a high flat fee which subsidises another
end-user such as Google etc. whose /16 generates ten thousand times
more queries for the anycast nameservers than their own.

In order to make this system run efficiently, in terms of scaling,
low delays etc. I think you would face many pressures to tightly
integrate the whole thing, from the outset, so it could be scaled
up, anycast, farmed out to ISPs who want to run their own anycast
servers etc.

In principle, I think you could make a global, distributed,
nameserver system for the /8 part of the query, with generally low
delay times and high query capacity.

The /24 query is a different matter.  If the nameservers for these
were run by end-users, then there would be a gaggle of them, and
only the keenest end-user would anycast their nameservers - to
spread load, provide robustness and to reduce response times.

One way to optimise the /24 response time is to unify the operation
of the nameservers for these as well.  This would require some kind
of consortium.  The most obvious first step is to run the /24
nameservers in the same rack as the /8 nameservers - and then
anycast the whole thing to the 36 locations mentioned above, and to
more as time goes on, including letting ISPs duplicate the whole
thing at their own expense wherever they like.

Now the operation of this scheme becomes technically and
administratively monolithic.  But this is clearly the way forward in
terms of improving robustness and reducing delay.

The /8 and the /24 servers in the same racks - so why not modify the
/8 ones, and make them talk to the relevant /24 one, to return the
complete answer with the response to the first query?

Then you only have one query and one response - at least halving the
total delay time in getting mapping.

It would probably be easier to rewrite the server to do this job
specifically, so while the software would create visible nameservers
for the various levels of sub-domain, including the /24 level, it
would be able to answer the whole query from the /8 level.  There
would need to be a large, unified, local database which the server
would query.  That could be on a separate machine in the rack, or
you could integrate the whole thing into a single bunch of software
on a single server.  Then, almost anyone could run one of these
things, as long as they had an rsync feed.

Now you have a genuine hybrid push-pull system of generally local
query servers around the Net, with fast (a few tens of milliseconds
in most cases, out to 100msec to 200msec at worst case for the most
remote ITRs) responses, and a single query and response.

This local and massively replicated anycast server system means you
can reduce the caching time of the responses, improving the ability
of ITRs to change their behaviour quickly according to the
end-user's needs.

Around this time, you will probably be thinking . . . if we could
only speed up the rsync system, we could enable the end-users to
have fast enough control of the ITRs to provide Mobility.

You would retrofit the system with a fast-push mapping distribution
system and arrive, by a circuitous path, at a system which supports
mobility and bears some resemblance to Ivip.

My plan is to start with fast push so we can support Mobility from
the outset, and have the mobile folks help pay for the mapping
distribution system!

This series of upgrades to TRRP has the advantage over Ivip in that
you are starting with a completely decentralised set of query
servers, using the ordinary DNS system and software - whereas Ivip
needs more protocol and software development and an up-front
deployment of servers by some sort of consortium to get started.

I like to think this can be done due to the enthusiasm generated by
a system which promises to fix the routing scalability problem,
provide many more end-users with multihoming, portability etc. (and
Ivip's TE options, which are less fancy than those of other
schemes), improve IPv4 address utilization and provide a gutsy, new,
highly valuable, kind of mobility.

>> Another critique is that this RIR server is going to be very
>> busy indeed.  You could anycast these /8 level servers, but
>> that would be costly and harder to administer, since they all
>> have to know so much about the authoritative nameservers for up
>> to 64k subdomains.
>> 
>> Broadly speaking, if there are about 220 /8s in use in IPv4,
>> then each such RIR server (really multiple servers) is going to
>> get 1/220 of the total global ITR initial requests for mapping
>> information.
>> 
>> Wouldn't it be more likely that the RIR gave a /12 of this /8
>> to some ISP, and would simply hand back an answer saying to ask
>> the nameserver of that ISP?  Then that server might delegate to
>> another one, which is authoritative.
> 
> Not if it harms performance. At one point the first letter of
> .com domains was reserved against the possibility that they'd
> need to do that sort of delegation but the operators chose
> anycast instead.

Anycast is a good way to scale the system up and reduce delay times.
 It has disadvantages in terms of being harder to detect problems
from afar, for instance if one of the anycast sites is unreachable
or not working properly.

>> looking at your IPv6 example in the same light, the figures are
>> more extreme.
>> 
>> Your first asked server is authoritative for a whopping /12 of
>> IPv6 space.  It gives an answer about what server to ask,
>> solving another 36 bits of the ITR's problem:  it tells the ITR
>> the address of another server to ask, which is authoritative
>> for a /48.
>> 
>> Do you expect this /12 server to know about (a theoretical
>> maximum) of 2^36 subdomains?  That is an awful lot.
> 

OK, those /12 servers are going to get a hammering, like the /8 ones
in IPv4.  Anycasting them would spread the load and reduce the
response time - but then you have to push the database to each
anycast site.

>> Overall, I question how your collapsing of what would otherwise
>> be a long series of lookups into two or three will be
>> problematic in terms of:
>> 
>> 1 - The business and therefore trust relationships probably go
>> in steps of fewer bits than the large jumps in bits you use in
>> the examples - raising questions of how the short-prefix
>> nameservers get to be reliably configured with so much detailed
>> information which is actually controlled by so many ISPs or
>> end-users.
> 

The optimal way of doing TRRP seems to be with a large number of
anycast query server sites which answer the full DNS query
immediately.  Therefore, the mapping database needs to be
distributed to every such site.  This involves a high degree of
collapsing what is initially conceived of as a delegated, widely
distributed, independently run, large set of nameservers into a
cleanly replicated set of anycast server sites, all dependent on
either a single feed of updates, or multiple feeds from different RIRs.

The technically optimal method involves a high degree of
integration, but perhaps you would work towards that as traffic
volumes rise, starting with a relatively ad-hoc, casual, set of
nameservers run by RIRs, ISPs and end-users.

With Ivip, I want to start with a lightweight version of the highly
integrated fast hybrid push-pull system - so from the outset it can
do Mobility and so it can grow to more and more sites for full
database ITRs and query servers, whilst retaining the original
structure.

>> 2 - How this collapsing thwarts the ITR's ability to cache a
>> larger number of nameservers which will actually be used in
>> subsequent requests - thereby requiring it to keep asking the
>> /8 (IPv4) or /12 (IPv6) servers time and again.  The same goes
>> for the world's ITRs and so these servers get a hammering.
> 
> The worst case of this problem is precisely the dot-com zone
> problem which is already solved and deployed at an operations
> level.

Do you have any references on how they do this?  I couldn't easily
find technical information on what software they use for the
nameservers, or how the .com database is maintained and somehow made
accessible to multiple registrars.

>> The real question is whether the delays inherent in an ALT or
>> TRRP based system are enough for at least some marketing folks
>> to trump it up to the broader end-user population as being
>> significant.
> 
>  bytes. You have to transmit more bytes with map-encap so it'll
> cost you more.
> 
> The marketing game is to make sure that at least some people see
> the advantage of selling the new capabilities. "With map-encap,
> we can sell you PI for $20/month. That loser who says map-encap
> is crap won't sell you PI for less than $2000. Two-kay. Twenty
> bucks. You tell me who's full of crap."

Sure - the people without $2k, $8k or whatever have no choice but to
use the map-encap scheme and, with TRRP or ALT, put up with initial
packet delays.

I am aiming for a map-encap scheme without significant initial
packet delays.   Then the existing big-time PI folks would be
encouraged to adopt the new kind of address space management.  Even
though it is their own already paid for PI space they would be
managing with Ivip or whatever, they would be able to slice and dice
it much finer than the prevailing (and likely to remain so) IPv4 BGP
system can, with its /24 256 IP address granularity.

This way, an existing end-user with a /16 who advertises it as
"multiple" longer prefixes can convert their system to an Ivip MAB,
which burdens the BGP system with only a single a single
advertisement.  That reduces the DFZ routing table by "multiple
minus 1" routes.  It also encourages new entrants to adopt
Ivip-managed address space, rather than hang out for conventional
BGP managed PI space "because that is what all the big boys use".

  - Robin

---

From: "William Herrin" <[email-masked]>
Date: Mon, 25 Feb 2008 10:02:00 -0500

Hi Robin,

In a word, yes. For all of the reasons you list in the long version of
your post, what you describe is a viable way of scaling up the middle
layers of the TRRP DNS hierarchy to handle pretty much any imaginable
projection of the routing system load. That scale-up is possible from
day-one, without needing to make any adjustments to the protocol.

There are at least a few other ways to scale the system up depending
on the balance between cost and performance that users are willing to
tolerate. Conveniently, these methods are all compatible with each
other so an AS who wants more performance can have it while an AS who
would prefer to push the cost down instead can have their wish too.
That moves the cost/benefit decision out of the architecture level and
in to the operations level where it belongs.

Here's some good news: it's unlikely that such a scale-up would ever
be necessary. The APT researchers report a miss rate under 1% for as
little as 4000 cached entries. Having worked with caching systems
before, this is not out of the ballpark. TRRP gains the same kind of
benefit, but deployed in COTS hardware with gigabytes of memory it can
maintain a substantially larger cache.

Even if caching failed us for some unforeseeable reason, we could
compose a v4.trrp.arpa consisting of the top 50k /24's and wildcards
to the /8 level NS servers for the rest. Such a cache-helper zone
could be pushed relatively cheaply to as many ASes as wanted it
without disturbing the protocol.

Here's some better news: the churn rate for these middle layers is low
enough that we could get away with pushing an update as rarely as once
a day. Once per hour is perhaps more likely for the sake of
convenience. Even if the operational realities incent us to push
updates to geographically dispersed servers, they'll be really cheap.

Remember, multihoming, traffic engineering and mobility happens at the
bottom layer of the TRRP hierarchy. The middle and top layers only
need to support major reconfiguration.

But even if we did end up having to push the data in the way you
describe, there is still no single device that has to handle move data
than COTS hardware is capable of. There are no $10M routers or map
servers required in TRRP's architecture no matter how far it scales.

>  complete answer with the response to the first query?

I suspect for the same reason the GTLD servers aren't modified to
query the second-level servers on behalf of requesters. But if
performance is sufficiently enhanced by such an activity it could be
done without changing the protocol.

>  have fast enough control of the ITRs to provide Mobility.

That's already tackled in a different direction with preemptive change
notification (PCN). http://bill.herrin.us/network/trrp-preempt.html

Two key tasks for a mobility system are:

1. Manage disconnection so that the systems with which a mobile device
is communicating don't quit communication while waiting for the device
to become available again.

2. Quickly push knowledge that a change in location has occurred out
to the systems with which the mobile device is communicating.

TRRP partially addresses #1. My best guess is that #1 would require
either a significant change in the IP stack or some landed station
would need to take over for the mobile station upon detecting
disconnection so that it could close the TCP windows and do similar
tasks which cause the servers communicating with the mobile station to
pause their transmissions without disconnecting. TRRP makes the latter
process relatively straightforward: simply change the ETR entry for
that mobile device.

TRRP directly addresses #2 with PCN. Because of the authentication
complexity, PCN doesn't push the change out to the ITRs using it.
Instead, it pushes only the knowledge that the cached entry is stale
and must be updated with a new query.

>  accessible to multiple registrars.

Dot-com and dot-net are generated out of a central SQL database
maintained by Network Solutions if I remember right. The various
registries have access to an API that lets them add and remove
information. An hourly dump is done into a zone file which is
distributed to the contractors running the gtld servers, some anycast
some not.

The details are probably buried in NSI's contract with ICANN somewhere.

>  Ivip needs more protocol and software development and an up-front
>  provide many more end-users with multihoming, portability etc.

I'd like to think so too, but the pragmatist in me won't allow it.
We'd have safe, efficient autodrive cars if only we had a passenger
car-sized rail system for them to run on. It's not that we couldn't
build such rails or even that they'd be more expensive to build and
maintain than asphalt roads. It's that we have a massive deployed
infrastructure of asphalt roads and no deployed infrastructure of
passenger car-sized rails.

Ideas can be revolutionary but infrastructure construction must by
necessity be evolutionary. It's like the way to Millinocket, "You
can't get there from here."

Regards,
Bill Herrin