Subject: [RAM] Tunnelling Route Reduction Protocol

From: "William Herrin" <[email-masked]>
Date: Mon, 20 Aug 2007 09:46:57 -0400

Hi folks,

For your amusement, the Tunneling Route Reduction Protocol with proof
of concept C code:

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

Regards,
Bill Herrin

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

_______________________________________________
RAM mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ram

---

From: Robin Whittle <[email-masked]>
Date: Tue, 21 Aug 2007 12:41:52 +1000

Hi Bill,

Here are some thoughts after I had a quick read of:

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

Very roughly, I think TRRP is like LISP 2, with a transitional
arrangement for continued reachability during introduction, with
longer-term administrative arrangements for removing prefixes of
mapped addresses from the global BGP routing table.

I think the biggest problem TRRP faces is that when a packet arrives
at an ITR which has no mapping information, that the ITR must hold
the packet until it gets that information.  Via DNS, I guess that
could take a second or two or more.  Generally, I think this is an
unacceptable delay, since the application which sent the packet will
assume the packet or its response is lost, and will send another
one.  I think this is one major reason why no-one is seriously
proposing LISP 2 as a solution to the routing and addressing
problems.  Another concern might be about overloading the DNS system
with  more tasks.

Your multihoming service restoration system seems to rely on the ITR
getting a "destination unreachable" response when it sends a data
packet.  Without this, the ITR assumes that the packet is received
by the ETR and that the ETR can send the packet to the final
destination.  I think this would be a poor way of ensuring that the
packets really do reach their destination.  "Destination
unreachable" packets could get dropped, and you would need to ensure
there was no filtering of such packets between all ITRs and ETRs.
Yet some networks like to drop "destination unreachable" packets to
reduce the ability of an attacker to probe the existence of hosts in
their network.  This might limit how deep the ETRs are located.  Yet
having a deeper placement of ETRs helps with scaling - spreading the
load among more of them.  Deeper, closer, ETRs also reduces the path
length to the destination host.

So like LISP and eFIT-APT, TRRP's multihoming service restoration
functions are hard-coded into the protocol and are implemented
independently by each ITR.

In contrast, Ivip has no built-in multihoming service restoration
functions.  It is up to the end user to choose and supply their own
monitoring system, which can be arbitrarily flexible, complex and
costly as they choose.  This system is then given the power to
control the mapping of their addresses.  The Ivip system simply
follows these instructions.  The ITRs do not attempt to determine
reachability or decide on alternative ETRs to tunnel packets to.

This makes the Ivip system a relatively simple component, to be used
with other user-supplied components, to achieve a variety of
benefits - multihoming, TE, portability and mobility with generally
highly optimal path length.

You don't explain how an ETR can get packets to the intended
destination.  Presumably they could do so via a tunnel, in which
case each host requires special software to decapsulate the packet.
 Otherwise, the ETR needs a direct link to each destination host, or
the local routing system needs to be able to route the packets with
their raw addresses (the IP address of the destination host).  You
would need to ensure that all packets addressed to the hosts with
TRRP mapped addresses were sent via an ITR (apart from those
emanating from an ETR).  This is because only the ITR can have the
latest information on where the packets should be sent to.  The
local routing system can't be expected to change so rapidly, or to
make multihoming service restoration decisions.  I think this is a
common problem for LISP and Ivip (eFIT-APT too?).

Also, I understand the outer packet source address of TRRP's
tunneled packets is that of the ITR.  This makes it very difficult
for ETRs to protect against spoofed local source addresses when they
decapsulate packets.  Ivip uses the source address of the sending
host as the source address of the outer IP header of the
encapsulated packet.  This enables the ETR to perform some simple
tests when decapsulating the packet, which extends the reach of the
network's border router's filtering of source address of incoming
packets, to solve this problem:

http://www.firstpr.com.au/ip/ivip/draft-whittle-ivip-arch-00.html#anchor67

 - Robin

---

From: "William Herrin" <[email-masked]>
Date: Tue, 21 Aug 2007 09:30:13 -0400

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

Hi Robin,

Thanks for your response.

> one.

This is true for packets which will leave the local AS and cross the
Internet. This brings up three points:

1. 99.9% of the time, the originator of the packet has already had to
do a DNS lookup or some other lookup to map a name to an IP address.
Doing another lookup for that first connection attempt leaves us in
the same ballpark speed-wise.

2. This delay only occurs the -first- time the ITR sees a packet for a
particular destination. After that, it has a destination cached. Even
re-lookups are background tasks. The ITR is permitted to keep the
destination cached long after the TTL expires. The only requirement is
that it initiate a background relookup the first time it sees another
packet for the destination.

3. Traffic within the AS (or the local portion of the AS for
particularly large AS's) need not enter TRRP at all. Barring a
passthrough-mode ITR close to the source, It moves normally as
dictated by an interior routing protocol.

>  I think this is one major reason why no-one is seriously

As always, the key portions of the root of the DNS tree get
immediately cached by the resolver. TRRP has its own branch in the
system, so as you get down to the components that are heavily used
with a short timeout, the servers can be scaled to match. One of the
benefits of using DNS for this is that we already have software which
scales up to a massive level with little pain.

> packet.

Actually, no. TRRP relies on the operator of the authoritative DNS
server performing some sort of monitoring to determine when a
particular ETR is no longer a reasonable target and then updating the
DNS records. When the records expire at the ITR (which is intended to
happen quickly) the relookup reveals a new destination.

This monitoring is not defined by the protocol. It can be as simple
(and slow) as "change by hand when there is a problem" or arbitrarily
complex.

Note that that the ITR has no other mechanism for detecting a failure
downstream from the ETR. If the ETR is reachable but it can't reach
the end-user network, the destination unreachable goes back to the
sender, not the ITR itself. Ideally this can be handled by allowing
the packet to drop into another ITR instead and be rerouted to an ETR
which does have a route to the destination.

Discovering the failure can be slow, taking up to the DNS TTL. The
destination unreachable stuff is intended to provide the ITR with a
shortcut to detect the failure sooner. The optional preemptive change
notification also helps speed the process up. When not available, the
regular timeout and relookup mechanism applies.

Also, where the ITR is operating in passthrough mode on an originating
host, TCP retransmits can be used to key a retry with an alternate
ETR. That's the primary point of having a passthrough mode. Doesn't
work through NAT though. That's unfortunate for IPv4. Should be a
non-issue for IPv6.

> This might limit how deep the ETRs are located.  Yet

ETRs can be as deep or shallow as the destination network operator
desires. They can sit just inside the AS if desired. Alternately, the
service provider could assign 2 addresses from globally routable space
to each customer and let the customer implement both the DNS server
and the ETR on customer's own network.

> destination.
> their raw addresses (the IP address of the destination host).

Correct, that's how it works during normal operations. Any place I
didn't specify otherwise, packets are intended to move via plain old
raw IP routing.

In the case where the ETR's link to the customer network has been
severed, the packet will ideally fall into another ITR and be rerouted
to an alternate ETR. This is not a protocol requirement but it would
shorten the recovery time after the loss of the link and before the
propagation of the new ETR information via DNS.

> tunneled packets is that of the ITR.

Correct.

> This makes it very difficult

Hmm. Would you jimmie up an example of aberrant behavior you feel
couldn't be adequately addressed within the ETR or ITR, or via
existing mechanisms for protecting against spoofed addresses?

Thanks again,
Bill Herrin

---

From: Robin Whittle <[email-masked]>
Date: Wed, 22 Aug 2007 00:42:51 +1000

Hi Bill,

Thanks for clarifying some things.

I understand - as I should have earlier - that your proposal
involves a separate set of nameservers, which can be scaled to deal
with the load of queries, including I guess by using anycast servers
in multiple locations, as with the root nameservers.

> (and slow) as "change by hand when there is a problem" or arbitrarily

OK - I understand from this that TRRP and Ivip are both relatively
simple "components" of the complete multihoming solution, with the
end-user supplying their own monitoring system to update the mapping
database.  That is my view of how your system would work, since
although you wrote:

> TRRP relies on the operator of the authoritative DNS
> particular ETR is no longer a reasonable target and then updating
> the DNS records.

I figure that either the operator of the DNS server covers address
space for many end-user networks, and that each end-user might want
to choose some monitoring system which is different from whatever
the DNS operator has available - and so would pay someone else to
run that monitoring service and tell the DNS operator what changes
to make to the mapping of their address space . . .  Or that the
authoritative controller of the DNS information (a subset of what a
whole server controls) is the end-user organisation themselves.

With Ivip, I aim to get those changes to ITRs within a few seconds.
 Your TRRP arrangement relies on cache time expiration, so the
response speed for multihoming service restoration needs to be
traded off against the amount of query traffic to the nameservers.

Ivip is pretty ambitious in this attempt to transmit mapping changes
to all the ITRs which need it so quickly.  If this can be done, then
it would support a mobility arrangement which I think can't be done
by any of the other proposals including with the slower arrangements
which I think your reliance on cache expiration require.

> sender, not the ITR itself. 

OK - so the ITR is not involved in this.  Some separate monitoring
system is required to find out which is the best ETR to use,
irrespective of whether traffic packets are being sent to the
destination host or not.

I don't clearly understand quite a few of the next paragraphs - but
it is late in the evening ....  I will read them again in the next
day or two.

> existing mechanisms for protecting against spoofed addresses?

Sections 14.1 to 14.1.2.5 cover this:

  - Robin

---

From: "William Herrin" <[email-masked]>
Date: Tue, 21 Aug 2007 14:25:04 -0400

Hi Robin,

That's essentially correct. It starts at the same root as everything
else but follows its own branch of the tree.

> database.

Correct.

> whole server controls) is the end-user organisation themselves.

Correct. I envision both operating mechanisms being used. I also
expect a market to develop for an optimizing server which offers
different answers depending on the source of the query, much like
companies such as Akamai do now for http content. Such a device could
take factors like latency, packet loss, the relative sizes of the
customer's upstream connections and current use data to optimize
traffic engineering.

Because its keyed to individual IP addresses, the traffic engineering
can extend all the way down to the host level if desired. Perhaps
you'll program the mail servers to prefer the least-cost path while
the web servers prefer the best performance path. Today this can only
be done at the coarse /24 level and then only by deaggregating and
polluting the DFZ.

> traded off against the amount of query traffic to the nameservers.

Correct, although there is an optional component that allows the
information to be propagated sooner, within a few seconds of the
change.

Correct.

> it is late in the evening ....  I will read them again in the next

Its more likely that I didn't explain myself well. I'll take another stab at it.

The ITR primarily relies on the TTL offered in the DNS response packet
to determine how long to cache the destination ETR before checking to
see if its still valid. Even if you set the TTL to something like 60
seconds, that means a slow recovery to failure. I don't tackle this
problem directly. Instead, I come at it from several sides:

1. ETR unreachable. The ITR ignores the TTL and performs a new lookup
immediately. If the DNS hasn't been updated yet, it discards the
unreachable ETR from the results and tries the next best.

2. No direct route to the Destination from the ETR. The packet moves
towards the default route inside the AS which ends at another "end of
the line mode" ITR. The ITR recognizes that there should have been a
local route for the packet. As a result, it re-encapsulates the packet
and sends it to the next best ETR which isn't local. This rerouting
continues briefly until the DNS is updated and the ITR's copy of the
DNS record expires.

3. No direct route to the Destination from the ETR. The ETR optionally
sends a preemptive change notification to the ITR, advising it that it
has no route to the destination. If the ITR is paying attention, it
eliminates the ETR as a candidate for that destination.
http://bill.herrin.us/network/trrp-preempt.html

4. DNS updated with new routes. The DNS server optionally sends a
preemptive change notification to all addresses which recently
requested the now-updated record. Where those DNS resolvers are also
the ITRs, they'll re-lookup the route.
http://bill.herrin.us/network/trrp-preempt.html

5. ITR is in "passthrough mode" rather than "end of the line" mode. In
passthrough mode, the ITR attempts to encapsulate packets but
retransmits them as raw IP towards the default route if it can't
quickly do so. Passthrough mode is intended for a NAT firewall or the
packet's originating host. These systems have state information about
a number of the protocols moving through them. The ITR component can
take a hint from lower-level retransmits and switch to an alternate
ETR if the chosen ETR isn't getting the job done.

The ITR has to be outside any NAT firewall for obvious reasons. As a
result, "passthrough mode" is of limited utility in IPv4. IPv6 has no
NAT, thus it should be possible to implement a passthrough-mode ITR on
every IPv6 host that wants to with the resulting improvement in
performance.

6. Simple case: the addresses are single-homed to a classic multihomed
organization. For example, a customer of one ISP where the ISP is a
DFZ participant. In this case, only one ETR is offered. Plain old BGP
finds the new route to the CIDR block containing the ETR. The ETR
itself is stateless; within the AS its address can be anycasted by any
ETR device capable of doing the job.

7. Silent death. Either the ETR or destination is unreachable but none
of the notifications make it back to the ITR. The destination remains
unreachable until the TTL on the DNS response that provided it
expires. The relookup is expected to withdraw the bad ETR and provide
a new valid ETR.

> http://www.firstpr.com.au/ip/ivip/draft-whittle-ivip-arch-00.html#anchor67

Thanks. I've read that, but I could use help constructing a scenario
that behaves aberrantly under TRRP.

For example, the ETR can be expected to filter packets claiming to be
both from and to an address on its local lan. No properly configured
ITR will generate such a packet. So, that case is eliminated as a
spoofing possibility.

Another example: an end-user org wants to stop spoofing at its
upstream border even though it has multiple LANs and ITRs operating in
passthrough mode. This remains possible. Implement a trivial
split-horizon DNS at the resolver so that internal addresses are
always directly routed. Then filter any packets with an internal
source address at the ETR. So, this case is eliminated as a spoofing
possibility.

A bad example: an ISP wants to stop spoofing at its upstream borders.
It can't do this for multihomed customers now. Packets from the
customer could legitimately arrive from somewhere other than the
customer's link.

What's an example of a case that isn't susceptible to spoofing in
today's network designs but would be susceptible with TRRP?

Thanks,
Bill Herrin

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 22 Aug 2007 10:32:38 +0200

On 2007-08-21 15:30, William Herrin wrote:
...
> the same ballpark speed-wise.

Wouldn't that be 49.95%? Half of all first packets tend to be
responses such as SYN/ACK that involve no DNS lookup. For a server
handling thousands of requests per second, adding a lookup means
holding thousands of TCBs in a wait state for the duration of the
lookup. There are perhaps some interesting DDOS attacks there.

    Brian

---

From: "William Herrin" <[email-masked]>
Date: Wed, 22 Aug 2007 18:41:43 -0400

On 8/22/07, Brian E Carpenter <[email-masked]> wrote:
> responses such as SYN/ACK that involve no DNS lookup.

Hi Brian,

Its still 99.9%; the return packet is part of the initial transaction.
But you're right, there are potentially two extra lookup delays on
that first transaction in addition to the original name to IP lookup.

If the network operator is sloppy then there could be more. If the DNS
resolver doesn't refer queries through a resolver on globally routable
space or the authoratative name to ip DNS server isn't on globally
routable space then there could be a dozen lookups to get to the point
where the two endpoints are talking and all pertinent routes are
cached.

That's avoided by good operations practice, so I'm not too worried about it.

> For a server

Shouldn't be much different that you see with SYN floods and SYN cookies now.

I suspect the worst DOS would involve sending packets to random
addresses. The ITR lookups run afoul of the same problem that Cisco
fast-switching did: overwhelming the cache. The ITR would have to take
care not to discard routes for sessions that have seen a lot of
packets in favor of pending lookups or routes that have only seen a
few packets.

Regards,
Bill Herrin