Subject: [RRG] Happiness; lack thereof

From: Iljitsch van Beijnum <[email-masked]>
Date: Fri, 7 Mar 2008 00:03:08 +0100

After a hiatus in reviewing drafts/proposals, I've been reading the  
LISP-APT draft.

I am not happy. Have we learned so little in the past years?

In a system where a fraction of all traffic requires more processing  
(i.e., the first packet in a session triggers setting up flow state,  
or in this case, initial packets for which there is no mapping are  
forwarded over a third infrastructure (the PA/core infrastructure  
being 1 and the ITR/ETR infrastructure 2)), then there will invariably  
arise a situation where the fraction of special case traffic is larger  
than what can be handled. If not for mundane reasons such as network  
use growing faster than hardware capabilities, then because of denial- 
of-service attacks. I had the pleasure of managing a router with a  
route cache when the slammer worm hit. It was dead in the water. An  
almost identical router that didn't use a cache was able to keep  
forwarding packets. This is a lesson we can't ignore.

Bringing all information to a central place doesn't scale. The number  
of entities at the top of the hierarchy must be limited in some way or  
another. In the case of NERD or APT this is almost trivially easy to  
accomplish by not using a monolithic database that holds all  
information for the entire internet, but by having an arbitrary number  
of sub-databases that each hold information about a distinct part of  
the address space, so mapping requests can be forwarded to the  
appropriate database and the databases can be updated in parallel  
without interdependency. Parallel is cheap and scalable, if it's easy  
to make your processing parallel, doing so is a no-brainer.

Implicit mapping requests should be considered harmful. Don't hide  
relevant information. The correlation between the need to send packets  
over the third infrastructure and lack of mapping state is not equal  
to 1, so treating the result of one as the other is a bad idea. ITRs  
know when they need to send mapping requests, so they should do so  
explicitly. This way, the mapping database doesn't have to do  
unnecessary work and a modicum of data and control plane separation is  
maintained.

Depending on return packets to indicate problems, such as the address  
for an ETR becoming unreachable, an ETR becoming unreachable or a  
destination "behind" and ETR becoming unreachable is way too  
dangerous. Path MTU discovery does this and it works quite poorly in  
practice. At a minimum, unreachables will be rate limited. They may  
also fail to be generated, be filtered or spoofed.

These are general comments, please apply them to proposals/solutions  
where the shoe fits.

On a more positive note: the mapping distribution in APT looks  
promising, it's just the more mundane nuts and bolts that are  
problematic.

--
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: Michael Meisel <[email-masked]>
Date: Thu, 06 Mar 2008 15:30:39 -0800

Hi Iljitch, thanks for a great post, I think it's really important we 
bring our discussion back up to higher-level issues like this if we're 
going to make progress. See my comments below.

> After a hiatus in reviewing drafts/proposals, I've been reading the 

I think you mean LISP-ALT. :-D

> over the third infrastructure and lack of mapping state is not equal to 
> 1, so treating the result of one as the other is a bad idea. ITRs know 
> when they need to send mapping requests, so they should do so 

This is worth exploring, but, in APT at least, there is no time that an 
ITR requests a mapping from a default mapper without also requesting a 
packet to be forwarded on its behalf. So it seems unnecessary.

> destination "behind" and ETR becoming unreachable is way too dangerous. 
> Path MTU discovery does this and it works quite poorly in practice. At a 
> minimum, unreachables will be rate limited. They may also fail to be 
> generated, be filtered or spoofed.

Though APT relies on return packets to indicate problems, I think we've 
addressed a number of these issues. First of all, we use normal IP 
packets for this purpose, so filtering is unlikely. The destination 
address for such packets comes from the mapping database, and the sender 
cryptographically signs these packets. The info that went into the 
mapping database was also cryptographically verified. So spoofing should 
be very difficult. Since it's part of the APT protocol, I don't see why 
these packets are any less likely to be generated than a BGP withdrawal 
today.

-Michael

---

From: "William Herrin" <[email-masked]>
Date: Thu, 6 Mar 2008 19:19:36 -0500

>  packet to be forwarded on its behalf. So it seems unnecessary.

Hi Michael,

The worm on Grandma's unsecured machine can pump 30kpps through a
properly configured $50 FiOS line at 2mbps. Each worm packet can have
a different, randomly selected destination IP address. If your APT
island provides a gig-e upstream from a neighborhood infested with 100
such worms, what happens when your default mapper gets hit with 3mpps?
It's only 200mbps of traffic after all.

A general purpose answer to this question that works for any such
system is: you build a protection device that will permit no more than
n packets per second from any one source IP address. As a result, the
mapper doesn't see 3mpps; it sees perhaps 10kpps total from the 100
worms and it can keep up with that. Each source is then constrained to
100 "new" destinations per second, but that's generally within bounds
for acceptable source behavior.

The architectural worry is this: how deep in the Internet core is your
mapper? If your mapper is close to the edge then with a protection
device there won't allow enough traffic to kill the mapper. If it's
deep then its share of the traffic from a hundred thousand worms are
going to take it down.

>  these packets are any less likely to be generated than a BGP withdrawal

I haven't dug through APT wrt this issue, so I can't speak with
authority here. I do note that as listed at
http://bill.herrin.us/network/statechange.html, Pulled Cache with
Change Notification DOES NOT guarantee that state change propagates.

A BGP withdrawal doesn't depend on any given packet reaching its
destination. If the neighbor fails to receive the withdrawal, the BGP
session stalls while the source retries. If completely unsuccessful,
the BGP session fails causing the neighbor to initiate a withdrawal of
ALL of the source's routes. This pattern propagates as far as needed.

Regards,
Bill Herrin

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

---

From: Michael Meisel <[email-masked]>
Date: Thu, 06 Mar 2008 18:04:33 -0800

Hi Bill, thanks for your questions. See below.

> deep then its share of the traffic from a hundred thousand worms are

Enforcing a maximum on new destinations per source address is much more 
easily and effectively done at TRs, which, in APT, are meant to be at PE 
routers of transit providers. The load at each TR should be manageable, 
and the excess traffic never reaches the default mapper.

> ALL of the source's routes. This pattern propagates as far as needed.

In APT, these notifications are data-triggered, so I don't believe APT 
suffers from this particular issue. If you have a chance to look at one 
of our documents, let me know if you agree.

-Michael

---

From: "Victor Grishchenko" <[email-masked]>
Date: Fri, 7 Mar 2008 10:28:22 +0500

>  and the excess traffic never reaches the default mapper.

I also did some worm-related troubleshooting and my intuition tells me
that something will surely explode in such an architecture. Just a
feeling, probably because you'll have to keep too much state per
packet or because end hosts will get another leverage over the routers
in terms of operations per packet...

200.000 entries in a routing table is a lot
200.000 packets is not much
200.000*40 bytes = 8Mb is just nothing

Finally, I cannot find why EID-to-RLOC cache is significantly smaller
(preferably, in terms of big-O) than the EID-to-RLOC database. Is
there any study of that issue?

-- 
Victor

---

From: Luigi Iannone <[email-masked]>
Date: Fri, 7 Mar 2008 11:32:27 +0100

Hi,

> there any study of that issue?
You can get a look to:

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

There you can find the size of a cache.
The size of the database, assuming granularity of prefixes annonced  
by BGP, is just the size of a BGP table.

Cheers

Luigi

Luigi Iannone

[email-masked]

---

From: Xu Xiaohu <[email-masked]>
Date: Fri, 07 Mar 2008 16:21:27 +0100

> in terms of operations per packet...

Reasonable, the default mapper will have to maintain a huge per-flow-based
status statistics table. What's the estimated amount of statistics for each
default-mapper? 

In fact, the DDoS attack risk is a common problem for almost all the
cache-ITR-based approaches, not just for APT.

Best wishes,
Xiaohu XU

---

From: "William Herrin" <[email-masked]>
Date: Fri, 7 Mar 2008 11:36:40 -0500

>  cache-ITR-based approaches, not just for APT.

Indeed. TRRP will have to address this by detecting the flood and
filtering packets from the sources. Its ITRs are close enough to the
network edge that the requisite amount of state it has to deal with to
do this is manageable.

In TRRP, this has the side benefit of rendering the TRRP address space
inaccessible to infested sources based on their packet-scattering
behavior. Scanning worms just won't work with TRRP. :)

Regards,
Bill Herrin

---

From: Michael Meisel <[email-masked]>
Date: Fri, 07 Mar 2008 14:05:06 -0800

> status statistics table. What's the estimated amount of statistics for each

Hi Xiaohu, I don't believe the default mapper needs to understand
anything about flows. When it gets a packet from an ITR, it simply 
examines the destination address and replies with a mapping, meanwhile 
encapping and forwarding the packet to the destination. Once the ITR 
receives the mapping, it doesn't make use of the default mapper again 
until it has another cache miss.

The default mapper keeps a small amount of state to ensure that it only 
responds once (or maybe twice) to a burst of traffic for the same (ITR, 
destination prefix) pair.

-Michael

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Sat, 8 Mar 2008 10:30:14 +0100

> I think you mean LISP-ALT. :-D

No, this one:

D. Jen, M. Meisel, D. Massey, L. Wang, B. Zhang and L. Zhang, APT: A  
practical tunneling architecture for routing scalability, February  
2008, http://www.cs.ucla.edu/~meisel/apt-rrg.pdf

See my message from january 28 for my ALT critique.  8-)

>> relevant information. The correlation between the need to send  
>> packets over the third infrastructure and lack of mapping state is  
>> not equal to 1, so treating the result of one as the other is a bad  
>> idea. ITRs know when they need to send mapping requests, so they  
>> should do so explicitly. This way, the mapping database doesn't  
>> have to do unnecessary work and a modicum of data and control plane  
>> separation is maintained.

> This is worth exploring, but, in APT at least, there is no time that  
> an ITR requests a mapping from a default mapper without also  
> requesting a packet to be forwarded on its behalf. So it seems  
> unnecessary.

Hm, what about the case where a host sends packet p1 to destination d,  
and the local ITR doesn't have mapping for d so it sends the packet  
down the third infrastructure and waits for a mapping reply. But  
before that mapping reply comes back, the host sends packet p2 also to  
d. The mapping server now gets packet p1 which requires a mapping  
reply, but it also gets packet p2, which doesn't really need to  
generate a mapping reply because the mapping reply to p1 will get  
there before the mapping reply for p2 anyway.

>> Depending on return packets to indicate problems, such as the  
>> address for an ETR becoming unreachable, an ETR becoming  
>> unreachable or a destination "behind" and ETR becoming unreachable  
>> is way too dangerous. Path MTU discovery does this and it works  
>> quite poorly in practice. At a minimum, unreachables will be rate  
>> limited. They may also fail to be generated, be filtered or spoofed.

> Though APT relies on return packets to indicate problems, I think  
> we've addressed a number of these issues. First of all, we use  
> normal IP packets for this purpose, so filtering is unlikely. The  
> destination address for such packets comes from the mapping  
> database, and the sender cryptographically signs these packets. The  
> info that went into the mapping database was also cryptographically  
> verified. So spoofing should be very difficult. Since it's part of  
> the APT protocol, I don't see why these packets are any less likely  
> to be generated than a BGP withdrawal today.

Well, we can have a discussion on the practical issues, which can of  
course be addressed one by one to varying degrees of satisfaction. But  
in my opinion, it's architecturally undesirable to depend on the  
behavior of a third party system for the communication to work. (I  
mean third party as in managed by a third party, obviously routers and  
DNS servers are generally required in addition to the end hosts.) When  
problems arise, you don't have much recourse. If the source is able to  
detect failures on its own, this is fundamentally more robust.

(There is of course the issue that the source has easy access to this  
knowledge because it's a byproduct of transport protocol activity. But  
systems in the middle, such as ITRs, don't have easy access to this  
information.)

---

From: Michael Meisel <[email-masked]>
Date: Sat, 08 Mar 2008 14:41:43 -0800

Iljitsch van Beijnum wrote:
>>> should do so explicitly. This way, the mapping database doesn't have 
>>> to do unnecessary work and a modicum of data and control plane 
> and the local ITR doesn't have mapping for d so it sends the packet down 
> the third infrastructure and waits for a mapping reply.

I think you may have misunderstood something fundamental to our design. 
There is no third infrastructure. Each transit AS that deploys APT 
deploys their own default mapper(s). Default mappers store the full 
mapping table, so even on the case of an ITR cache miss, no third party 
is involved in data forwarding.

> But before that 
> mapping reply comes back, the host sends packet p2 also to d. The 
> mapping server now gets packet p1 which requires a mapping reply, but it 
> also gets packet p2, which doesn't really need to generate a mapping 
> reply because the mapping reply to p1 will get there before the mapping 
> reply for p2 anyway.

We have a deaf timer in default mappers to prevent a burst of traffic 
from generating a burst of mapping replies. It still forwards the 
packets, but the mapping replies get rate limited. We do this at the 
default mapper to (1) keep the ITRs as simple as possible, and (2) make 
sure misconfigured ITRs can't bog down the default mapper.

>> we've addressed a number of these issues. First of all, we use normal 
>> IP packets for this purpose, so filtering is unlikely. The destination 
>> address for such packets comes from the mapping database, and the 
>> sender cryptographically signs these packets. The info that went into 
>> the mapping database was also cryptographically verified. So spoofing 
>> should be very difficult. Since it's part of the APT protocol, I don't 
>> see why these packets are any less likely to be generated than a BGP 
>> withdrawal today.
> 
> behavior of a third party system for the communication to work. (I mean 
> third party as in managed by a third party, obviously routers and DNS 
> servers are generally required in addition to the end hosts.) When 

There's no third party -- the party that sends the failure notification 
is the transit AS containing the ETR. They are the transit provider for 
the destination, and therefore have an incentive to make sure their 
customers' traffic gets rerouted in the case of a failure.

At the risk of re-stating the obvious: fundamentally, we are just 
replacing the mechanism by which transit networks learn about 
connectivity changes to edge networks. That is, today, all edge network 
connectivity info is propagated via BGP. APT (like any Map & Encap 
scheme) takes edge networks out of the transit networks' BGP tables. But 
they still need to know about connectivity changes so they can pick a 
working ETR. But we don't want to propagate everything like BGP -- we 
would put back most of the control traffic we are trying to remove.

-Michael

---

From: Xu Xiaohu <[email-masked]>
Date: Mon, 10 Mar 2008 09:57:28 +0100

> -----邮件原件-----
> 发件人: [email-masked] [mailto:[email-masked]] 代表 Michael Meisel
> 发送时间: 2008年3月7日 23:05
> 收件人: Xu Xiaohu
> 抄送: Routing Research Group
> 主题: Re: [RRG] Happiness; lack thereof
> 
> Xu Xiaohu wrote:
Hi Michael,

What you said is right. I should have said the ITR should maintain
per-source-destination-pair statistics table as an attack-proof method.

Best wishes,
Xiaohu XU