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

[Robin Whittle <rw@firstpr.com.au>]

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 rrg-request@psg.com 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