[Ndn-interest] Label swap vs PIT (was Re: Largest DDoS attack ever delivered by botnet of hijacked IoT devices)

Greg White g.white at cablelabs.com
Thu Oct 6 11:17:26 PDT 2016

I’m not sure if this specific idea has been explored before, but we came up with another PIT-less approach earlier this year after considering the Bloom-filter based approaches.  It seemed to us that the Bloom filter approach was perhaps too clever for its own good, and that a simpler approach might have better characteristics (e.g. zero false positives and trivial computational complexity).

Given that the vast majority of forwarders (maybe all) will have less than 256 faces, the value of N would almost always be 1, and thus the maximum size (in bytes) of the face-stack would effectively be D (where D is the diameter of the network or AS), and the average size of the face-stack would be d/2 (where d is the average path length).    The Bloom-filter approaches seem to use BF sizes of 16 or 32 bytes, which is likely larger than d/2 (and perhaps even larger than D).  Also, while it would be slightly more complex to implement, face labels could even be an integer number of bits rather than bytes, which would make the average face-stack only k*d/2 bits (where k is log2(average(degree)) ).


From: Ndn-interest <ndn-interest-bounces at lists.cs.ucla.edu> on behalf of Muhammad Hosain Abdollahi Sabet <mhasabet at gmail.com>
Date: Thursday, September 29, 2016 at 6:19 PM
To: Marc Mosko <Marc.Mosko at parc.com>
Cc: "ndn-interest at lists.cs.ucla.edu" <ndn-interest at lists.cs.ucla.edu>, "christos at colostate.edu" <christos at colostate.edu>
Subject: Re: [Ndn-interest] Label swap vs PIT (was Re: Largest DDoS attack ever delivered by botnet of hijacked IoT devices)


There is nothing in JJ's latter proposal in ICN 2016 indicating anchors' identifiers are not anchors' names. Actually the namespaces could be the same. So name lookup can still hold.


On 29 Sep 2016 10:11 am, <Marc.Mosko at parc.com<mailto:Marc.Mosko at parc.com>> wrote:
In the earlier label-swapping proposals, some of which are JJ’s, it is true that the Interest is routed per-hop via the name and the labels are established only to label swap back the Data.  The state space scales in the number of flows through a node.

In some of the later proposals, such as the paper JJ just presented at ICN 2016, because the routing is done on anchors one no longer needs to do a lookup on names at every hop, but on anchor identifiers.  I think it also went further in that once a forward path label is picked for an Interest, it could be label swapped in the forward direction too (assuming an SVC was already setup for that destination).  In this respect, the switching of interests and data inside the network is no different and only the edge devices need to do different computations on them.


On Sep 29, 2016, at 9:47 AM, Luca Muscariello <luca.muscariello at gmail.com<mailto:luca.muscariello at gmail.com>> wrote:

I think the PIT is not just a question of interests aggregation. It is more than that.
We need to be careful in comparing forwarding and the way routing is/can be built  on top of a given forwarding plane.

I read JJ's paper but not yet Gene's and Ravi's.
If Ravi's can send a preprint that would help the discussion.

Of course I would expect the authors of such papers to make the comparison we look for in the papers.

Why is the PIT more than just aggregation?

In CCN only Interests are routed. Data is in a way label switched by using local state. The name in the data is used to implement label switching and to follow the bread crumbs. But in principle you could use a token to implement data forwarding.
Still this token state space would scale with the interest names state space.

So the label switching proposed by JJ scales better because the system has changed state space of the labels. JJ is using an address space and not a name space. The assumption is that the address state space is way smaller. And it is true.

So the big change in JJ design is this one and not label swapping per se.

I read other papers proposing that like Carzaniga's work (ICN 2014) but I would like to read Gene's work and also Ravi's work to see how the solved the issue.

Now routing on locators is a whole new thread I guess. But PIT-less design that route on names is different. Again I need to check the new papers.


On Thursday, 29 September 2016, <Marc.Mosko at parc.com<mailto:Marc.Mosko at parc.com>> wrote:
This message got a bit off topic from the OP, so I label swapped the subject ;)

I think preserving the possibility of symmetric paths is a significant feature.  It is the main property that new congestion control protocols use and I think an attribute that deserves serious thought.

I agree with Luca that going label swapping instead of PIT trades one set of features for another set of features.  I think it would be useful to systematically list the features offered by the PIT and the features offered by label swapping.  One could then make a principled comparison between them.

I believe that the main feature lost is Interest aggregation.  If one has caching, then I think this is a minor loss.  The window for Interest aggregation to work is a RTT.  The window for caching to work could be much longer.  All the memory one was spending on the per-packet PIT state can now be used for more caching.  It would be useful to look at flash crowd dynamics to see if even in those cases aggregation saves much compared to caching.

In the NDN architecture, one would also lose the PIT nonce state, but NFD already has a second nonce table to keep them around after a PIT entry is erased, so that could stay as it is.  It wouldn’t be exactly like now, but one could probably make nonces still work if one thinks keeping them is worth the memory usage.

A significant feature gained is a large reduction in memory bandwidth by not having to update a large data structure at wire speed.  As we saw today from JJ’s presentation, if one uses label swapping and routing on anchor identifiers, then one can make the case of running on today’s forwarding hardware at or near full speed.  Thus the time to deployment on high speed routers could really shrink down.

Anyway, I think this is worth more formal study rather than this piecewise analysis.


On Sep 29, 2016, at 5:26 AM, GTS <gts at ics.uci.edu> wrote:

To get back to the issue of having or not having the PIT:

Recall that this thread started with discussion of massive DoS attacks on
the current Internet, initiated from IoT devices. It progressed to a discussion
of DoS attacks in CCN. It was then suggested that a PIT-less
design might address the only glaring major type of DoS attack in CCN --
interest flooding. I specifically say "address", not "solve" or "obviate".
(That's because even a PIT-less design allows the producers to be interest-flooded).
Now, the particular PIT-less design that Cesar mentioned is this:


It is NOT motivated solely by interest flooding mitigation. It just happens
to be one of its features. The authors (of whom I'm one) would love to
hear some reasoned criticism of this PIT-less design. It should be based
on actually reading the paper.

More generally, the PIT is currently a fundamental feature of both NDN and CCNx.
Should it even be questioned? To some true believers, this is clearly an anathema.
IMHO, all architecture features should be up for debate and all dogmas ought to be questioned.
For example, I believe that the PIT and the CACHE (for example) are not what
make an architecture Content-Centric. Either or both can be removed and what
remains would still be a Content-Centric Network (though perhaps not a good one).

Finally, the PIT-less design mentioned above could well be ill-advised,
or even totally senseless. We simply don't know yet.
Indeed, as the paper admits, it has some problems of its own.
Or, it might make sense in some settings, e.g., where the
network infrastructure is mobile. Or, it might be an alternative/optional implementation.
(BTW, it can in fact co-exist with a PIT-ful CCN).



Gene Tsudik

Chancellor's Professor of Computer Science

University of California, Irvine

On 9/27/16 10:12 PM, Luca Muscariello wrote:
The work JJ has presented this morning is probably another interesting thread.
And I agree that the signal mentioned here is not a prerogative of the PIT.

So, to stay in topic to this thread, from my point of you what JJ has proposed
has more compelling properties to remove the PIT than the DDoS example
considered here.

In JJ's proposition, you trade something for something else. It's not an equivalent
architecture to NDN though. So we need to be careful before laying away pieces of the architecture. There is a  price for that.

On Wednesday, 28 September 2016, <Marc.Mosko at parc.com> wrote:
Removing the PIT and using, for example, a label swapping approach such as J.J. Garcia-Luna-Aceves has suggested, does not remove the “signal” you talk about.  One could keep upstream and downstream counters for each label swap identifier and see which labels are not getting downstream data.

I do not think the strategy of purging PIT entries based on the shortness of their remaining lifetime gives you any correlation to purging attack packets.  First of all, an attacker could easily use a very large Interest Lifetime.  Well-behaved clients that are using RTT estimates in their Interest Lifetime would, by definition, likely have very small margins in the Interest Lifetime remaining  before the Data comes back (personally, I think it is a problem to make InterestLifetime based on RTT, but that’s a different thread).


> On Sep 28, 2016, at 10:47 AM, christopherwood07 at gmail.com wrote:
> On September 27, 2016 at 5:14:14 PM, Christos Papadopoulos
> (christos at colostate.edu) wrote:
>> On 09/27/2016 04:59 PM, woodc1 at uci.edu wrote:
>>> To re-iterate Cesar’s point, as of now, there is no truly effective
>>> interest flooding mitigation. However, one concrete way to minimize
>>> the attack surface (for routers) is to get rid of the attack's root
>>> cause: the PIT. (Producers could still be hosed with bogus interests.)
>>> And since the PIT enables several important functions, other
>>> architecture changes will probably have to follow in its wake.
>> You start with what I believe to be the wrong premise: protecting the
>> router. In NDN we care about communication, not a single router.
>> Protecting a router is winning the battle but losing the war.
> I respectfully disagree. If the adversary takes out the producer,
> there is no communication. If the adversary takes out the routers
> adjacent or otherwise on the path to the producer, there is no
> communication. Protecting the router(s) is equally important,
> especially since it may impact more than just a single producer.
>> I don't understand your statement that the root cause of DDoS attacks is
>> the PIT. The root cause of DDoS is resource exhaustion.
> In these attack scenarios, the PIT *is* the resource being exhausted.
>>> Personally, I don’t think we should settle with an architectural
>>> element that has a known (and quite severe) weakness simply because it
>>> enables some nice features in practice. The more serious design
>>> problems must be dealt with first, not last.
>> You are underestimating the importance of the signal the PIT provides.
>> It is an important insight into the status of communication. The PIT
>> does not simply enable some "nice features". Think a bit harder about
>> the things you can do with this signal.
> In most attack scenarios, yes, it tells you when bogus interests are
> flooding a particular prefix and otherwise when communication is
> failing. But consider this scenario. Suppose you have a malicious
> producer cooperating with one or more malicious consumers. The
> consumers are quickly sending interests to this legitimate producer,
> who responds with legitimate data. The communication is not failing.
> Their goal is to do nothing other than saturate the PIT of some
> intermediate router. Per Spyros’ follow-up suggestion, that router
> might kick out old, legitimate interests in favor of these malicious
> ones. Of course, this is fundamentally how we would expect one to deal
> with and manage a limited resource. So preventing this attack seems
> difficult for any approach. But the point is that this resource, the
> PIT, is easily abused in CCN/NDN.
> Chris
> _______________________________________________
> Ndn-interest mailing list
> Ndn-interest at lists.cs.ucla.edu
> http://www.lists.cs.ucla.edu/mailman/listinfo/ndn-interest

Ndn-interest mailing list
Ndn-interest at lists.cs.ucla.edu


Ndn-interest mailing list

Ndn-interest at lists.cs.ucla.edu


Ndn-interest mailing list
Ndn-interest at lists.cs.ucla.edu<mailto:Ndn-interest at lists.cs.ucla.edu>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.lists.cs.ucla.edu/pipermail/ndn-interest/attachments/20161006/c8e2b864/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Face-StackCCN.pdf
Type: application/pdf
Size: 438886 bytes
Desc: Face-StackCCN.pdf
URL: <http://www.lists.cs.ucla.edu/pipermail/ndn-interest/attachments/20161006/c8e2b864/attachment.pdf>

More information about the Ndn-interest mailing list