Saturday, August 16, 2008

SIGCOMM 2008, Part 2

The Accountable Internet Protocol (AIP) paper asks the question: what if we re-architectured the Internet to start with self-certifying addresses, so that there was a layer of accountability -- you'd know where packets are coming from. This paper clearly fits square in the mold of the NSF FIND program. They suggest what a self-certifying architecture would look like, how routing would work with such an architecture, consider potential attacks on the proposed architecture, and discuss whether technology trends would make such an architecture feasible. Certainly interesting, although I admit to high-level unsubstantiated concerns about the specific address architecture they propose. (I suppose as a "kid" I saw too many key-exchange-style protocol papers where a subtle flaw was exposed by a subsequent paper...)

I notice they used a Bloom filter in the paper without even giving a citation. Have Bloom filters now become so successfully widespread in the networking community that no citation is needed? What a nice thought! (Or maybe the authors just ran out of space for the citation.)

Another SIGCOMM paper continues on the path set out by for example Feigenbaum, Papadimitriou, Sami, and Shenker, on using game theory to study the behavior of BGP. They propose a more realistic model (where, for example, Autonomous Systems can be paid for attracting traffic) which, naturally, leads to more negative results in terms of the truth-telling behavior of ASes. (Why is reality so often disappointing this way?)


Anonymous said...

Hi Michael,

I'm an author of the AIP paper. It didn't even occur to me that to provide a citation for a Bloom filter! I think it has become almost as commonplace in networking as a hash table. That said, a citation would've been a good idea.

I'd be curious to hear about any specific concerns you have about the security properties (or anything else) of the scheme itself.


Michael Mitzenmacher said...

Hi Hari. I'm happy to hear a Bloom filter is now considered standard. :)

And I apologize if I sounded negative -- definitely no specific concerns. I just remember a time in my life reading a bunch of key exchange protocol papers, and then reading lots of subsequent papers claiming that there were subtle "bugs" in the originals, and have been left with nagging suspicions when I see similar types of works. But that shouldn't be taken as a specific comment on specific suspicions of your paper!

David Andersen said...

As Hari noted, thanks for the head-bonk about the missing Bloom filter citation. Thanks to the miracle of online publication, I've updated the version we host on my papers page and on the AIP web page to include a citation, which miraculously fit without wrapping to the next page.

Michael Mitzenmacher said...

David (and Hari) --

Boy, now I feel guilty. You don't have to cite Bloom if you don't want to! (I mean, it's a Bloom filter, people should be able to figure it out. :) )

It's kind of an interesting question when an algorithm or data structure becomes just such a part of the standard lexicon that it doesn't need to be cited because it's now "background knowledge". I'm happy to think Bloom filters have reached that point. (Though I'd be more convinced if there were actually a standard undergraduate text that included it...)

David Andersen said...

No, no, I totally agree with you. I think that Bloom filters have established themselves among the graduate-level networking consciousness, but it still seems worthy of citing. We were having a discussion at SIGCOMM about this, actually, observing that many networking papers cite Pei Cao's proxy cache peering paper ("summary cache") for bloom filters, since that was the paper that introduced them to the distributed systems community. Best to get people in the habit of citing Bloom before we stop citing it at all!