Subject: Re: [lisp] uRPF as a possible solution

From: [email-masked] (Noel Chiappa)
Date: Mon, 25 Jul 2011 15:42:13 -0400 (EDT)

> From: Jeff Wheeler <[email-masked]>

    > If the xTR does not have the necessary state to forward a packet, it must
    > communicate with the MS infrastructure. As cache hit rate goes down,
    > direct MS involvement in forwarding operations goes up.

To a certain point, yes... but we do _already_ have rate-limits on the
ITR->resolution_system, precisely to protect the resolution system.

I mean, imagine a scenario where an ITR gets taken over by a bad guy - or,
simpler yet, a bad guy claims to be an ITR when they are not. The attacker
could then generate as much traffic to the resolution system as they want;
they are a direct threat to the resolution system, i.e. not via churning the
cache on an ITR. The best cache management in the world cannot prevent such
direct DoS attacks on the mapping infrastructure. So such threats exist
irrespective of DoS attacks on caches, i.e. have to be protected against
directly

All sorts of DoS attacks are possible. Imagine a system in which all ITRs have
all mappings (e.g. through NERD, or something like that). So a DoS attack there
would consist of having a number of sites update their mappings at high rates.
(That would be an even better attack, since it's a multiplier attack - i.e.
each attack packet would produce an expanding cascade of pacekts, at the syetem
attemtped to update every ITR in the world with the new mapping.)

Build any system, I can think of a DoS attack on it... (Are people DoS'in DNS
servers yet, BTW?)

To deal with DoS attacks, any system ideally i) degrades service for other
clients under the load, but doesn't keel over dead, and ii) allows you to track
down the source(s) of the attack and deal with them. (Preferentially by taking
the perpetrators and throwing them into vats of boiling oil... but I digress.)

	Noel

---

From: [email-masked] (Noel Chiappa)
Date: Sat, 30 Jul 2011 11:51:35 -0400 (EDT)

{I have to go out soon, but before I go, a quick answer to this part: the
later part of your message - which is most interesting! - I will get to after
I have had more time to think about it.}

    > From: Patrick Frejborg <[email-masked]>

    > On Thu, Jul 28, 2011 at 7:15 PM, Noel Chiappa <[email-masked]>
    > wrote:

    >> Yes and no. For _most_ sites, no, since their access patterns (even
    >> for servers) are to a limited share of the Internet, therefore much
    >> less than a full table. Also, BGP (like any 'push' system) distributes
    >> _everything_ to _everyone_, regardless of whether they need it or not.
    >> Any data at any ITR (even if it's a cITR at a content provider, with
    >> lots of data) is there because it is _actually going to be used_.

    > Believe you are saying that DNS-stylish distribution for rITRs and
    > BGP-stylish distribution for cITRs...

Not really (although perhaps, now that I think it through - see below); let
me try and say it more clearly:

First: for _all_ sites (no matter what size a share of the 'complete' mapping
table their access pattern means they have to have), any data at their ITR(s)
is there because it is _actually going to be used_. This is unlike BGP,
which, _for any machine which is not sending packets to every destination on
the Internet_, it is receiving _some_ data it has no use for.

Yes, for the few sites which have to have the entire table (or very close to
it), they are i) not going to save any space, and ii) 'push' might be more
efficient than 'pull' if you have to do have the entire database. But how
many sites will that be, really? Which leads me to...

Second: For _most_ sites, even some/many of those which _are_ serving content
(i.e. not just clients), their access patterns are to a limited share of the
Internet. This is driven by several forces, including language, etc.

Take for example the traces used to drive the simulations done for caching
effectiveness (in LISP and LISP-TREE - I'm too lazy to look up the titles, I
can get them if you need them). One of those traces was for a very large
university (Université Catholique de Louvain), with about 30K students and
staff. Universities tend to host a lot of content - albeit content that's not
as popular as Youtube! Still, one would expect the _access patterns_ to that
data to be pretty widespread (with the internationalization of the knowledge
'industry'), even if the _volume_ is much lower. (Yes, as you turn up the
amount of accesses, the pattern will spread a bit, as you get a bit of 'fill
in', but it's not going to expand to the entire mapping 'table'.) However, I
think the pattern shown in those traces (IIRC, maximum cache size was about
1/10th of the Internet) is going to hold for _most_ sites, including
many/most content sites.

It would be very interesting to look at the ecommerce site of a major
retailer, and see if they have a similar pattern. For those selling actual
physical things, I'll bet most would be similar (no matter how high the
traffic volume), simply because most retailers have limited distributions
networks (often limited to a single country, or a small number of countries)
for the actual physical goods. There may be a few exceptions (maybe Amazon?),
but they are the exception, I expect - and even then I doubt they are selling
to the entire world/Internet. Yes, retailers for purely electronic goods
(music, etc) would not have this limitations - but there are not many of
them, compared to the others.

Yes, the Youtubes, etc of the world are really going to be exceptions (and
they are going to have to have almost full tables), but those sites already
have very specialized infrastructure. Perhaps a hybrid 'push-pull'
distribution for mapping data (as in, a deliberate load of the entire table,
but pulled, rather than pushed, a la BGP) would be the way to go for them?
But that is just speculation.

(An interesting observation about terminology: 'push' and 'pull' can be
broken down into two axes: i) 'how much', and ii) 'how'. What we normally
divide into two - 'push' and 'pull' - are actually only two boxes out of the
four defined by those orthogonal axes. I just referred to a third ('all'
and 'retrieve'), and there is a fourth ('some' and 'send'), which I cannot
think of any use for!)

	Noel