Subject: [RRG] thoughts on the design space 3: caching

From: Jari Arkko <[email-masked]>
Date: Thu, 24 Jul 2008 15:23:10 +0300

One of the conclusions that I drew from our exercise was that caching 
mapping resolution is the culprit for many of the issues. Deterministic 
packet delay/drop, for instance. And the source of most of the 
complexity. Can we rethink some of the solutions in this light?

It seems that we have bundled the design of our encapsulation and 
mapping protocols with the way routers arrange their forwarding cache.

First, I am not at all convinced that we actually HAVE to employ a cache 
for the forwarding lookup. The designs such as LISP are based on the 
idea that a subset of routers has to do more work than most routers in 
the Internet. This may be all that is needed; build those routers with 
the capability to have a full table. The rest of the routers will only 
need minimal amount of memory. If you believe this, then something like 
LISP + NERD would be far simpler and efficient than the other alternatives.

Hasn't the industry built caching routers before, and what happened to 
them? Think we need a second try? I have not seen any ideas on how to 
remove the problems inherent with the caches, such as vulnerability to 
being hit by random destination addresses.

Second, even if you believe that we DO need a cache, there's really no 
reason why the cache design has to be cast into the rest of the 
architecture. Even if your forwarding ASIC can't employ enough memory 
for all the entries, I have a hard time convincing myself that we can't 
have a general purpose computer sitting next to it that holds the full 
table. I'm writing this on a laptop that has a 160G disk. That would be 
enough for several mapping tables containing EVERY IPV4 ADDRESS.

Third, if you believe we must use an alternate topology for routing the 
initial packets while we are fetching for the cache entry, is that 
alternate topology a global infrastructure or a local device? Again, I 
have hard time getting myself convinced that we need to build a global 
infrastructure. The cost of the infrastructure is immense, and if you 
use the current BGP infrastructure you end up keeping there precisely 
the information that you wanted to get rid of. My take is that if you 
cannot build an ITR/ETR that holds the entire mapping table in memory, 
maybe it would be better to attach it to a general purpose computer that 
can (slowly) handle the cache misses and hand the packets back to the 
router.

Jari

--
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, 24 Jul 2008 09:20:38 -0400

On Thu, Jul 24, 2008 at 8:23 AM, Jari Arkko <[email-masked]> wrote:
> architecture. Even if your forwarding ASIC can't employ enough memory for
> all the entries, I have a hard time convincing myself that we can't have a
> general purpose computer sitting next to it that holds the full table. I'm
> writing this on a laptop that has a 160G disk. That would be enough for
> several mapping tables containing EVERY IPV4 ADDRESS.

Jari,

You make an assumption here: that the ID->Locator map can be made to
remain static over a reasonable period of time. In other words, the
map would only change when someone contracts a new ISP to provide one
of the loctators that reaches them. Ephemeral changes to routing due
to link failures and the like would impact the topology RIB but not
the map. Were this not the case, the amount of static storage would be
irrelevant because you'd have to be able to push updates to the map to
reflect current ID reachability via each registered locator.

Unfortunately, this assumption is trivially demonstrated to be false.

Disconnection between a node and one or more of it's locator-trees
will be a routine event. A local T1 drops. Boom, disconnected. For the
map to remain static, something up the locator tree would need to be
able to -reliably- return a negative acknowledgment to the ITR
indicating that the node is not currently reachable via that locator.

But we already know negative acknowledgments can't be made to generate
and return reliably during an outage event. In any operational system,
we get unexpected routing loops or a firewall blocks the way or a
router malfunctions or the network is congested or something else
happens so that the packet is silently dropped without a NAK.

That's why we detect outages through the absence of positive
acknowledgment instead.

Regards,
Bill Herrin

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

---

From: Jari Arkko <[email-masked]>
Date: Thu, 24 Jul 2008 16:50:57 +0300

Bill,

There are potentially multiple levels of information here. There is the 
global map, be it from NERD or any other global system and it needs to 
be fairly static. E.g., a mapping from an identifier space into the 
addresses of the ITRs. Then there is a separate, more dynamic 
information which has to do with the current preferences and status of 
those ITRs.

Jari

---

From: "William Herrin" <[email-masked]>
Date: Thu, 24 Jul 2008 10:51:43 -0400

On Thu, Jul 24, 2008 at 9:50 AM, Jari Arkko <[email-masked]> wrote:
> global map, be it from NERD or any other global system and it needs to be
> fairly static. E.g., a mapping from an identifier space into the addresses
> of the ITRs. Then there is a separate, more dynamic information which has to
> do with the current preferences and status of those ITRs.

Jari,

You meant to say ETRs, right? The map that indicates which IDs are
reachable from which tunnel Exits?

I could swear I had this out with someone else just a few months ago.
The following scenario illustrates the problem:

Node X declares in the map that he is reachable from both ETRs A and
B. In fact, A and B are physically also routers belonging to two
different ISPs while X is physically a router at a customer site. X is
connected to A via a T1 data circuit labelled AX and to B, via a T1
data circuit labelled BX. Somewhere out there is an origin ITR we'll
call O. A is closer to O than B, so O normally sends packets to X via
A.

Link AX fails. Now what?

Solution #1: When A receives a packet for X from O, A sends a NAK back
to O informing it that X is temporarily unreachable via A. THIS DOES
NOT WORK. The character of the failure may prevent A from realizing
that X isn't reachable. The character of the failure may allow O to
think that X is still reachable via A even though A is malfunctioning
and will silently drop packets for X. The character of the failure may
allow O to think that A is still reachable even though packets to A
are silently dropped. In each case, the operator at X has no recourse
through which he can advise ITRs like O that he is temporarily
unreachable via A.

Solution #2: When A receives a packet for X from O, A reroutes the
packet to B for delivery to O. THIS DOES NOT WORK. Same reasons.

Solution #3: When X realizes that it no longer has a reliable
connection to A, it updates the map to reflect that it is no longer
reachable via A. THIS WORKS.

What's solution #4? What allows an end-node operator to cut out a
temporarily flaky upstream without updating the map?

Let me put it another way: you can't reliably get an automated list of
what -isn't- working right because, guess what, they aren't working
right! What you can reliably get is a list of things that -are-
working right. Can I get a "duh?"

Regards,
Bill Herrin

---

From: Xu Xiaohu <[email-masked]>
Date: Fri, 25 Jul 2008 11:20:06 +0800

Hi Jari,

> being hit by random destination addresses.

I believe the cache mechanism is still useful. However, it depends on what
you indeed expect it to do. If you just expect it to optimize the forwarding
path for the traffic, it would be OK. If you expect it to forward almost all
traffic, it would be doubtable. In other word, is it acceptable for the
overlay to forward most traffic once the cache becomes unavailable, e.g, the
cache is filled up due to some attacks.

> enough for several mapping tables containing EVERY IPV4 ADDRESS.

There is a similar idea with VA, that is, the full DFZ route is hold by
every router in its RIB, while only parts of the RIB will be installed into
its FIB. What's your opinion on this?

> can (slowly) handle the cache misses and hand the packets back to the

In VA, the FIB can be distributed just within a single AS. So there is no
need for a global infrastructure in fact. What's your opinion on this?

Xiaohu Xu

---

From: Xu Xiaohu <[email-masked]>
Date: Fri, 25 Jul 2008 11:34:37 +0800

> cache is filled up due to some attacks.

By the way, IMO, it also depends on how you use it. For example, a single
(or several) packet(s) can trigger a route entry in the cache, or only those
flows which have reach some rate can trigger a route entry in the cache.

Xiaohu XU

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 24 Jul 2008 22:26:07 -0700

> One of the conclusions that I drew from our exercise was that  
> caching mapping resolution is the culprit for many of the issues.  
> Deterministic packet delay/drop, for instance. And the source of  
> most of the complexity. Can we rethink some of the solutions in this  
> light?
>
> First, I am not at all convinced that we actually HAVE to employ a  
> cache for the forwarding lookup. The designs such as LISP are based  
> on the idea that a subset of routers has to do more work than most  
> routers in the Internet. This may be all that is needed; build those  
> routers with the capability to have a full table. The rest of the  
> routers will only need minimal amount of memory. If you believe  
> this, then something like LISP + NERD would be far simpler and  
> efficient than the other alternatives.

As you might now, LISP can work with a cache or a table. We have shown  
that with the various mapping proposals that have been documented.

> Hasn't the industry built caching routers before, and what happened  
> to them? Think we need a second try? I have not seen any ideas on  
> how to remove the problems inherent with the caches, such as  
> vulnerability to being hit by random destination addresses.

The BGP data indicates that out of 250K stored routes, most routers  
use only 25K of those routes. So isn't that a bit of wasted memory as  
well as come-up convergence time?

> Second, even if you believe that we DO need a cache, there's really  
> no reason why the cache design has to be cast into the rest of the  
> architecture. Even if your forwarding ASIC can't employ enough  
> memory for all the entries, I have a hard time convincing myself  
> that we can't have a general purpose computer sitting next to it  
> that holds the full table. I'm writing this on a laptop that has a  
> 160G disk. That would be enough for several mapping tables  
> containing EVERY IPV4 ADDRESS.

That is correct. The capacity is not the issue. It's getting the data  
there and updating it when it changes.

> Third, if you believe we must use an alternate topology for routing  
> the initial packets while we are fetching for the cache entry, is  
> that alternate topology a global infrastructure or a local device?  
> Again, I have hard time getting myself convinced that we

What do you mean?

> need to build a global infrastructure. The cost of the  
> infrastructure is immense, and if you use the current BGP  
> infrastructure you end up keeping there precisely the information  
> that you wanted to get rid of. My take is that if you cannot build  
> an ITR/ETR that holds the entire mapping table in memory, maybe it  
> would be better to attach it to a general purpose computer that can  
> (slowly) handle the cache misses and hand the packets back to the  
> router.

LISP can do both Jari. It's not wedded to one way or the other.

Dino

---

From: Jari Arkko <[email-masked]>
Date: Fri, 25 Jul 2008 09:50:47 +0300

Dino,

> LISP can do both Jari. It's not wedded to one way or the other.

I realize that. I'm not trying to criticize LISP or any other solution 
dataplane solution. I think I said in the initial mail that LISP + NERD 
would not have this problem. But I see a fairly broad design space -- we 
COULD do anything, but what SHOULD we do? I think it would be useful to 
narrow this down.

In particular:

- caching is responsible for a number of problems people have with the 
solutions
- there does not seem to be a compelling reason that the caching-or-not 
design should affect the architecture
- FIB caching is something that you could do in today's routers if you 
wanted to

Jari

---

From: Dino Farinacci <[email-masked]>
Date: Fri, 25 Jul 2008 09:33:31 -0700

> I realize that. I'm not trying to criticize LISP or any other  
> solution dataplane solution. I

I know you're not.

> think I said in the initial mail that LISP + NERD would not have  
> this problem. But I see a

It is not at all clear if it is a problem. In fact, I'll argue on some  
points it could be a feature.

> fairly broad design space -- we COULD do anything, but what SHOULD  
> we do? I think it would be useful to narrow this down.
>
> In particular:
>
> - caching is responsible for a number of problems people have with  
> the solutions

There are 100s if not 1000s of designs all over computer science and  
electronics that use caching. Some have failed and some are in  
mainstream use.

> - there does not seem to be a compelling reason that the caching-or- 
> not design should affect the architecture

Well, one thing this list keeps doing is trying to draw the line where  
architecture should stop leaving it for some other process, say  
engineering, to make the really hard decisions. If the architecture is  
too high-level and doesn't "draw a line in the sand", then the  
practical architecture will happen after this step in the process.

So you can't punt very many things or you become irrelevant.

Dino

---

From: Jari Arkko <[email-masked]>
Date: Fri, 25 Jul 2008 19:16:04 +0100

Dino,

> points it could be a feature.

Sure. I don't want to make an argument that the delay/drop 
characteristics of caching are horrible. In fact, while I know this is 
an issue, I do not have any information about whether it is of 
significant practical consequence. This why I'm asking you to find a 
test for this in EXPLISP.

> So you can't punt very many things or you become irrelevant.
This is true, and I'm very eager to make the decisions about details 
that matter. For instance, encapsulation, how the mapping function 
works, etc. However, based on what I said in my initial mail, I'm not 
sure caching is one of those details. It seems that you can implement 
caching without impact, for instance, the mapping system. And you can 
implement FIB caching in today's routers with today's Internet 
architecture if you want. If you believe that is necessary then maybe 
you should do that. But I believe the RRG should be more concerned with 
the details that HAVE to be agreed upon.

Jari

---

From: Olivier Bonaventure <[email-masked]>
Date: Fri, 25 Jul 2008 20:39:26 +0200

Jari,
> test for this in EXPLISP.

I'm also not convinced that the mapping delay matters on real networks 
provided that the granularity of the mapping replies is sufficiently 
large. In this case, the mapping service is only contacted once for the 
first packet towards the corresponding EID prefix. In most networks, 
most of the traffic is sent towards a small number of prefixes, see e.g.

http://inl.info.ucl.ac.be/publications/implications-topological-properties-i
http://inl.info.ucl.ac.be/publications/implications-interdomain-traffic-char

Thus, the ratio ( number of packets waiting for mapping reply) / (total 
number of packets) will be very low

We did simulations based on Netflow traces on a 1Gbps link connecting 
10.000 users and assuming that the mapping replies are for BGP prefixes, 
the amount of mapping request is reasonable. See e.g.

http://inl.info.ucl.ac.be/publications/cost-caching-locatorid-mappings

The only case where you would detect problems with mapping are when a 
single host is opening a single TCP connection. In this case, the SYN 
packet will be delayed by the mapping. Note that using the DNS also 
causes such a delay...

If EXPLISP needs to perform an evaluation, I would suggest to perform 
the evaluation based on packet traces or netflow traces as we did and 
not only on lab experiments with limited traffic.

Olivier

-- 
http://inl.info.ucl.ac.be , UCLouvain, Belgium

---

From: Dino Farinacci <[email-masked]>
Date: Fri, 25 Jul 2008 12:20:30 -0700

> I'm also not convinced that the mapping delay matters on real  
> networks provided that the granularity of the mapping replies is  
> sufficiently large. In this case, the mapping service is only  
> contacted once for the first packet towards the corresponding EID  
> prefix. In most networks, most of the traffic is sent towards a  
> small number of prefixes, see e.g.

Excellent point Olivier.

Dino

---

From: "Tony Li" <[email-masked]>
Date: Fri, 25 Jul 2008 14:44:53 -0700

|The BGP data indicates that out of 250K stored routes, most routers  
|use only 25K of those routes. So isn't that a bit of wasted memory as  
|well as come-up convergence time?

I believe that this isn't an accurate characterization.  From the data that
I've seen, most routes are being used.  However, I could easily believe that
many, many routes could be eliminated if we were able to aggregate
maximally.

Dino, if you have pointers to primary data sources to the contrary, could
you please post them?

Tony

---

From: Marshall Eubanks <[email-masked]>
Date: Fri, 25 Jul 2008 18:13:41 -0400

> many, many routes could be eliminated if we were able to aggregate

I could believe a factor of 2 easy - there is almost that much in
known deaggregation in each CIDR report.

--- 25Jul08 ---
ASnum    NetsNow NetsAggr  NetGain   % Gain   Description

Table     275468   173778   101690    36.9%   All ASes

A factor of 10 seems a little much to me, though.

Regards
Marshall

---

From: Dino Farinacci <[email-masked]>
Date: Fri, 25 Jul 2008 16:13:05 -0700

> Dino, if you have pointers to primary data sources to the contrary,  

There are plenty of operators on this list who can publicly comment. I  
talk to a lot of customers and that is the number they state. I have  
to protect their identity due to confidentiality agreements.

Dino

---

From: "Tony Li" <[email-masked]>
Date: Fri, 25 Jul 2008 16:32:15 -0700

|> Dino, if you have pointers to primary data sources to the contrary,  
|> could
|> you please post them?
|
|There are plenty of operators on this list who can publicly 
|comment. I  
|talk to a lot of customers and that is the number they state. I have  
|to protect their identity due to confidentiality agreements.

Fair enough.  If folks would like to contact me privately and in confidence,
I would appreciate that.  Until then, I remain unconvinced.

Tony

---

From: Jari Arkko <[email-masked]>
Date: Mon, 28 Jul 2008 22:53:19 +0100

Olivier,

> not only on lab experiments with limited traffic.
Indeed, that would be the reasonable way to do it. I'm glad to learn 
that you've done some evaluations already! (Is there a chance that you 
could talk about some of your experiments in EXPLISP?)

I am having network trouble accessing the papers for some reason, but I 
wanted to point out two specific things that I'm worried about.

First, we often see a heavily tail in traffic distributions. While a 
large network concentrates much of its traffic to a small set of 
destinations (say, google, microsoft, and youtube), there is a very 
large set of other destinations as well that some small number of users 
are accessing. I'm pretty sure I'm the only one accessing certain 
domains in the IETF network, for instance.

Second, I'm not necessarily worried about the DNS lookup + SYN case, and 
I don't believe the impact on that is very significant. As was stated 
earlier, DNS already introduces some delay. But I'm more worried about 
situations such as applications that do round-robin or failover over a 
set of servers. The servers might come from DNS at that point, be 
resolved much earlier, or be communicated from someone else as IP 
addresses (such as would often be the case in P2P systems). What are the 
effects on those applications?

Jari

---

From: Luigi Iannone <[email-masked]>
Date: Tue, 29 Jul 2008 11:04:32 +0200

Jari,

Le 28-juil.-08 à 23:53, Jari Arkko a écrit :

> Olivier,
>
>> The only case where you would detect problems with mapping are  
>> when a single host is opening a single TCP connection. In this  
>> case, the SYN packet will be delayed by the mapping. Note that  
>> using the DNS also causes such a delay...
>>
>> If EXPLISP needs to perform an evaluation, I would suggest to  
>> perform the evaluation based on packet traces or netflow traces as  
>> we did and not only on lab experiments with limited traffic.
> Indeed, that would be the reasonable way to do it. I'm glad to  
> learn that you've done some evaluations already! (Is there a chance  
> that you could talk about some of your experiments in EXPLISP?)
>
We already presented the results at RRG in Chicago. But we can redo  
the presentation without any problem.

Luigi

> I am having network trouble accessing the papers for some reason,  
> but I wanted to point out two specific things that I'm worried about.
>
> First, we often see a heavily tail in traffic distributions. While  
> a large network concentrates much of its traffic to a small set of  
> large set of other destinations as well that some small number of  
> users are accessing. I'm pretty sure I'm the only one accessing  
> certain domains in the IETF network, for instance.
>
> Second, I'm not necessarily worried about the DNS lookup + SYN  
> case, and I don't believe the impact on that is very significant.  
> As was stated earlier, DNS already introduces some delay. But I'm  
> more worried about situations such as applications that do round- 
> robin or failover over a set of servers. The servers might come  
> from DNS at that point, be resolved much earlier, or be  
> communicated from someone else as IP addresses (such as would often  
> be the case in P2P systems). What are the effects on those  
> applications?
>
> Jari
>
>
> --

Luigi Iannone

[email-masked]