Subject: [RRG] DNS Map: Mapping Resolution Combining Pull/Push Advantages

From: Christian Vogt <[email-masked]>
Date: Tue, 26 Feb 2008 10:57:25 +0200

Folks,

previous discussions on this mailing list have identified two main
types of mapping resolution, pull and push systems, both with their
respective benefits:

- Pull systems have comparably low state requirements, enabling finer-
   granular and dynamically generated mappings (e.g., for mobility)

- Push systems have comparably low resolution latency, and hence less
   packet loss in tunnel routers that buffer packets during resolution

I would like to propose DNS Map [1], a DNS-based mapping resolution
system that combines advantages of push and pull systems.  DNS Map
exploits the non-critical time hosts spend waiting for a domain name
resolution, by "pre-fetching" the mappings that tunnel routers are
likely to need in the immediate future.  This allows DNS Map to support
the low state requirements and fine-granular/dynamic mappings of pull
systems, while in many cases limiting mapping resolution latency to
that of push systems.

[1] http://users.piuha.net/chvogt/pub/2008/vogt-2008-dns-map.pdf
     or via RRG homepage

Your comments and opinions will be highly appreciated.

- Christian

--
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: Tue, 26 Feb 2008 09:14:56 -0500

>  [1] http://users.piuha.net/chvogt/pub/2008/vogt-2008-dns-map.pdf

Hi Christian,

Four comments:

1. Fetching the map alongside the the hostname presents a nasty cache
poisoning problem. The hostname response is not necessarily coming
from a server authoritative for the address map and the resolver has
no way to know the difference without performing additional lookups.

2. Prefetching the map in this manner assumes that the ITR uses the
same DNS resolver as the client. Unless the ITR is on the client, that
could get hairy fast.

3. Typical behavior of DNS resolvers assume that equal-priority
records can be reordered at will and they often do. You're asking for
the map records to be implemented in a way that is inconsistent with
that behavior.

4. If you haven't already read TRRP, you should:
http://bill.herrin.us/network/trrp.html . TRRP uses DNS in much the
way you propose and has already ground through a lot of the problems
you're likely to encounter.

Regards,
Bill Herrin

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

---

From: "William Herrin" <[email-masked]>
Date: Tue, 26 Feb 2008 11:29:30 -0500

>  likely to need in the immediate future.  This allows DNS Map to support

Christian,

I should qualify my prior post: I think your idea for pre-fetching the
map is interesting.

There are a couple things you'll need to do to make it work:

1. The DNS resolver has to make a second query for the EID MAP once it
knows the EID. Looking to the authoritative server for a particular
entry is how DNS resolvers verify that the the result is authentic.

2. The DNS resolver needs to determine whether a particular EID is
directly available in the routing system or whether it needs a map.
This could be done by giving the resolver a routing feed or by
including a record in the additional section of the DNS response for
the hostname that means a map lookup is required. The routing feed is
probably better. The latter would create some administrative overhead
and a split horizon problem because the address is directly available
in some parts of the 'net (e.g. those on the near-side of the ETR) and
only available via a map in others.

3. The DNS resolver needs a way to laterally query the caches of
nearby resolvers. That way if the ITR uses a different resolver than
the client but the resolver happens to be nearby, the ITR's resolver
can still get a hold of the pre-fetched map. Currently a recursive
query will cause the neighboring resolver to go out and fetch the
records while a non-recursive query will cause it to return only
authoritative records.

If you do all this then whatever the round trip time is between the
resolver and the client, you get about that much of a head start on
the map pull. If the client happens to be 150 ms away on a dialup, you
could well have the map by the time the client's TCP SYN reaches the
ITR. If the resolver is 20ms away over broadband, you probably won't
but you will have a 20ms head start.

Prefetch in the original style you describe could also be used in some
other non-DNS pull-based mapping system where a different
authentication approach would allow the hostname lookup to return both
the address and the address map. That would imply replacing the DNS as
a deployment prerequisite.

Regards,
Bill Herrin

---

From: Christian Vogt <[email-masked]>
Date: Sun, 2 Mar 2008 15:05:27 +0200

Bill,

thanks a lot for your comments.  I think, however, there is a basic
misunderstanding.  Let me clarify:

DNS Map handles mapping resolution /separately/ from regular domain
name resolution.  It uses separate DNS queries and different DNS
resource records.

Regular domain name resolution continues to be pursued by hosts or,
on their behalf, by DNS servers.  Mapping resolution may be performed
by Six/One routers (you called them "ITRs").  But for the benefit of
deployment flexibility, DNS Map does not stipulate who should perform
mapping resolution.  It may be performed by another network entity
that makes the mappings available to Six/One routers afterwards.

This is why neither the use of different DNS resolvers in hosts and
Six/One routers, nor reordering of equal-priority resource records,
nor caching should be a problem.

Let me know if this helped.

- Christian

---

From: Christian Vogt <[email-masked]>
Date: Sun, 2 Mar 2008 16:30:14 +0200

Bill -

> I should qualify my prior post: I think your idea for pre-fetching
> the map is interesting.
>
> 1. The DNS resolver has to make a second query for the EID MAP once
> it knows the EID. Looking to the authoritative server for a particular

Not sure I understand your comment right.  Do you recommend that a
mapping should always come from the same (authoritative) DNS server
as the EID?

FWIW:  DNS Map already does separate DNS queries for domain name
resolution and for mapping resolution.  A or AAAA records are requested
in the former, MAP records in the latter.  And MAP records can be
requested by EID or domain name.  (MAP record retrieval by domain name
is used in pre-fetching.)

> directly available in the routing system or whether it needs a map.

Discovery of whether a mapping is needed for a given EID can be handled
through mapping resolution if you assume that mappable EIDs are always
mapped in packets that cross an edge network border.  The existence of
a mapping for an EID is then equivalent to the need to map the EID.

What you suggest in addition is a means to allow an edge network with
mappable EIDs to be reached without mapping by other networks in its
proximity.  And yes, using a routing feed to achieve this would be
possible.  I would prefer this to be handled as an optional  
optimization,
however, because it can be deployed locally and without special support
from the mapping resolution system.

> nearby resolvers.

Right, this would be an optimization to reduce latency.  Specifically,
it would help taking advantage of pre-fetching more often.

There are two approaches of "pre-loading" an ITR with the mappings it
may need in the near future.  It is up to an edge network which approach
to follow, and how to specifically implement it:

- An ITR itself pre-fetches mappings for a given domain name upon a
   trigger.  This trigger could be a regular DNS query for that domain
   name, being forwarded by the ITR.  It could also be a trigger from a
   local DNS server resolving that domain name on behalf of a client.

- A different network entity than the ITR pre-fetches mappings and makes
   them somehow available to the ITR.  It could push the mappings to all
   local ITRs, or have an ITR pull the mappings when the first data
   packet needs to be mapped.

The DNS Map paper actually considers both of these cases.

> other non-DNS pull-based mapping system [...]

That's correct.  Pre-fetching is a mapping resolution technique that
applies to pull systems in general.

Thanks!
- Christian

---

From: "William Herrin" <[email-masked]>
Date: Sun, 2 Mar 2008 12:18:18 -0500

Hi Christian,

You talk about initiation by the DNS server for prefetching when it
sees an A record query. This is an interesting idea. For it to work,
some component of your mapping system will need to interact with the
DNS server that performs the A-record query.

>  mapping should always come from the same (authoritative) DNS server

Even if you look up something like "www.herrin.us MAP?" instead of
accepting the MAP as an additional record to the AAAA response, HOW DO
YOU KNOW what EIDs the authoritative server for herrin.us is permitted
to offer MAP records for? If you blindly trust that the information is
correct, a rogue DNS server can take over traffic from your system.

The DNS authentication model says that you know because any record
retrieved from the authoritative server for herrin.us MUST end in
herrin.us and any record which does not MUST be discarded by the
resolver. In your model, the query for "www.herrin.us MAP?" returns
"ABC::1 MAP 1.0.0.1". ABC::1 does not end in "herrin.us".

You don't magically know which server is authoritative to herrin.us.
You know because the resolver asked a root server "What servers are
authoritative for www.herrin.us" and it told the resolver, "These
servers are authoritative for .us". Then the resolver asked one of
these servers, "What servers are authoritative for www.herrin.us" and
it told the resolver, "those servers are authoritative for herrin.us."

How do you follow that authority chain for a map record for ABC::1
when you don't yet know that www.herrin.us has a AAAA for ABC::1?

>  nor caching should be a problem.

When you ask the DNS guys to add MAP records to the protocol, one of
the early things they'll tell you is: record ordering is not the
responsibility of the DNS server or the DNS protocol. If your
application requires the records in a particular order then the MAP
records themselves should designate that order.

If you're going to use DNS, why go against the grain?

>  applies to pull systems in general.

What I mean is that if you designed a pull-based mapping system in
which response authentication was not tied up in the query hierarchy
then your prefetching during the name lookup could work as you
envision. DNS is NOT such a system.

Perhaps you might use cryptographic signing by a certificate authority
so that a response record can be authenticated independently of the
query or source. In such a system, you'd have to supply several
cryptographic elements in the response from the authoritative server:

1. An address scope of authority statement signed by the address
authority indicating that a particular public key is valid for
authenticating map records within a given CIDR block.

2. A MAP record in the CIDR block signed by the private key for which
the public key is valid.

This approach has three obvious drawbacks:

A. It requires more bytes than can comfortably fit in a 512 byte
payload for a standard DNS response so if you want to keep things
efficient you're necessarily into a new protocol, not just something
layered on top of DNS.

B. It requires each resolver to maintain a truly massive CRL since
every time an address space is redelagated the old certificate has to
be revoked.

C. The resolver has to run a relatively slow cryptographic algorithm
for each and every response.

Regards,
Bill Herrin

---

From: Xu Xiaohu <[email-masked]>
Date: Tue, 04 Mar 2008 14:38:50 +0100

Hi Christian,

Provided that the mapping resolution is performed by hosts, what should the
mapping entry be? EID-based mapping entry (e.g.10.1.1.1/32) or
EID-prefix-based mapping entry (e.g.10.1.1.0/24)? If the former is adopted,
there will be a big challenge on the cache size of ITR, if the latter is
adopted, how can the ITR trust the mapping that hosts provide?

Best wishes,
Xiaohu XU

---

From: Christian Vogt <[email-masked]>
Date: Wed, 5 Mar 2008 12:33:22 +0200

Hi Bill!

> DNS server that performs the A-record query.

Right, interaction with the DNS server is one option.  Another option
would be to have tunnel routers initiate prefetching when they forward
an A-record query.

> correct, a rogue DNS server can take over traffic from your system.

I understand now what you mean:  The problem is that the owner of a  
domain name could respond with an ID-locator mapping that covers ID  
space from a different entity. To eliminate this threat, your would  
have to get the mapping from the owner of the ID, and this can only be  
ensured by keying the query with an ID.

Therefore, as you suggest, mapping resolution by domain name ("pre- 
fetching") will have to become a two-step process in DNS Map:  first,  
get the ID for a domain name; second, resolve that ID to locators.   
The second step may return the locator prefixes for an entire ID  
prefix, but that is fine because you know that the DNS server  
providing these locator prefixes is authoritative for the ID prefix.

No modification in DNS Map is needed for mapping resolution by ID.

> records themselves should designate that order.

Alright.  I guess a priority field in MAP records would do the job.   
It would allow MAP records to be reordered arbitrarily without losing  
priority information.

> envision. DNS is NOT such a system.

Right.  Do you agree that, with the modifications discussed above,
DNS Map would work?

Thanks for taking the time to discuss this, Bill.

Best regards,
- Christian

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Sun, 9 Mar 2008 08:43:57 -0400

On Tue, Feb 26, 2008 at 10:57:25AM +0200,
 Christian Vogt <[email-masked]> wrote 
 a message of 34 lines which said:

> system that combines advantages of push and pull systems.

After reading your document, I fail to understand how the DNS query is
constructed, when the "key" is an EID (if it is an host name, there is
no problem).

You say that the key of the lookup can be a single address or a
prefix. In the latter case, how do you encode it in the query?
Remember that the DNS has no concept of "longest match". The query on
the left-end side of the request ("query name" in DNS parlance) must
match *exactly* the left-hand side of the resource record ("owner
name"). So, whatever the encoding you use, you will have either to try
all possible prefix lengthes, or to know by some unspecified means the
prefix length (unless we decree that the length of 48 in RFC 3177 is
now mandatory).

A more detailed description of the representation of queries and
resource records would help the DNS people to understand what you
propose.

Figure 1 in your document did not help. Network A wants to contact EID
ABC::1. But the figure shows its ITR performing a query for
1000::1... The figure seems to contradict the text. 

Yours, very confused. But I'll be there on tuesday morning, you'll be
able to teach me :-)

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Sun, 9 Mar 2008 09:08:12 -0400

On Wed, Mar 05, 2008 at 12:33:22PM +0200,
 Christian Vogt <[email-masked]> wrote 
 a message of 71 lines which said:

> It would allow MAP records to be reordered arbitrarily without
> losing priority information.

Should you do so, remember that RFC 2782 already specifies such a
mechanism so it could be a better idea to build on it, specially since
it is already implemented in resolvers (for instance the RULI
library).

---

From: "William Herrin" <[email-masked]>
Date: Sun, 9 Mar 2008 12:43:18 -0400

Hi Christian,

Probably, yes. But why would you want to take this approach?

I chose DNS as the mapping system for TRRP because it allows me to
start deploying without having to first deploy map-server software.
Given a choice between a new DNS record type (which requires a
redeployment of updated DNS software before the rest of your system
can be deployed) or building an entirely new map protocol, I think I
would have chosen the latter. Now that I've been exposed to your
prefetch idea, I'm sure of it.

I don't think being able to start the map pull when the hostname
lookup starts outweighs the advantage of an already-deployed map
server system but it surely outweighs the advantage of merely having
most of the software already built.

>  it is already implemented in resolvers (for instance the RULI

Hi Stephane,

Using SRV records might introduce an additional lookup delay that I'm
sure Christian would like to avoid. SRV does, however, provide an
excellent model for setting priorities on response records.

Regards,
Bill Herrin

---

From: Christian Vogt <[email-masked]>
Date: Tue, 18 Mar 2008 14:40:29 +0200

Stephane -

Thanks for your review of DNS Map!  I also very much enjoyed our
face-to-face discussion in Philly.  It's good to have you in RRG.

> constructed, when the "key" is an EID (if it is an host name, there is

If the key is an EID, the query will be for reverse DNS.  Does this
answer your question?

> prefix. In the latter case, how do you encode it in the query?

The lookup key is always for a specific host, i.e., either a domain
name or an address.  The MAP resource records themselves may contain
aggregated information, however.  They include (in the RDATA field) a
pair of edge address prefix and transit address prefix -- although
prefix lengths may be 32 bits (IPv4) or 128 bits (IPv6) to enable
non-aggregated, per-host mappings.

A DNS query for a particular edge address then returns all
MAP resource records for which the edge address prefix includes the
edge address from the query.

The owner name of the returned records is set to the lookup key from
the query.  Depending on the DNS server implementation, the owner name
may be filled in dynamically given the lookup key in a DNS query, or
MAP resource records must be replicated for each possible owner name.
  The latter can typically be accomplished via macros, which many DNS
servers provide to generate resource records for a range of owner
names.

> 1000::1... The figure seems to contradict the text.

Thanks for catching this.  The ITR should perform a query for "ABC::1"
instead of "1000::1".

I am going to revise the document based on your review.

- Christian

---

From: Christian Vogt <[email-masked]>
Date: Tue, 18 Mar 2008 17:12:08 +0200

> it is already implemented in resolvers (for instance the RULI

Yep, point taken.

- Christian

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Tue, 18 Mar 2008 17:05:04 +0100

On Tue, Mar 18, 2008 at 02:40:29PM +0200,
 Christian Vogt <[email-masked]> wrote 

> If the key is an EID, the query will be for reverse DNS.  Does this

Yes. So, if you want to know the locator for the EID ABC::1, assuming
someone delegated sixone.arpa, the first Sixone router would query
1.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.c.b.a.0.sixone.arpa. Correct?

> aggregated information, however.  They include (in the RDATA field)
> a pair of edge address prefix and transit address prefix -- although

I am not sure how it could work. Another solution would be to use
aggregation and DNS wildcards. Assuming that ABC::/56 is handled by
the transit address (the address of the ETR in LISP) 1000::1, just add
in the DNS zone file:

*.0.0.0.0.0.0.0.0.0.0.c.b.a.0.sixone.arpa. MAP 1000::1

and that's all, requests for the MAP of ABC::1, ABC::42:1,
ABC::34:56:CAFE:6 would all yield 1000::1.

[Limitation: the resolution is one digit, that is 4 bits. So, you can
handle /56 prefixes but not /55.]

An ANSWER=0 (no MAP records) could mean that the EID is not an EID but
a RLOC.

> Depending on the DNS server implementation, the owner name may be
> filled in dynamically given the lookup key in a DNS query, or MAP
> resource records must be replicated for each possible owner name.

This is also possible.

> servers provide to generate resource records for a range of owner

You do not need DNS server support, the zone files can be preprocessed
by the macro system before being giving out to the DNS server.