The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.
Aalto

BloomCasting for Publish/Subscribe Networks

Mikko Särelä

Doctoral dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the School of Electrical Engineering for public examination and debate in Auditorium S4 at the Aalto University School of Electrical Engineering (Espoo, Finland) on the 14th of June 2011 at 3 o'clock p.m.

Overview in PDF format (ISBN 978-952-60-4149-0)   [1470 KB]
Dissertation is also available in print (ISBN 978-952-60-4148-3)

Abstract

Publish/subscribe has been proposed as a way of addressing information as the primary named entity in the network. In this thesis, we develop and explore a network architecture based on publish/subscribe primitives, based on our work on PSIRP project. Our work is divided into two areas: rendezvous and Bloomcasting, i.e. fast Bloom filter-based forwarding architecture for source-specific multicast. Taken together these are combined as a publish/subscribe architecture, where publisher and subscriber matching is done by the rendezvous and Bloom filter-based forwarding fabric is used for multicasting the published content.

Our work on the inter-domain rendezvous shows that a combination of policy routing at edges and an overlay based on hierarchical distributed hash tables can overcome problems related to incremental deployment while keeping the stretch of queries small and that it can solve some policy related problems that arise from using distributed hash tables in inter-domain setting.

Bloom filters can cause false positives. We show that false positives can cause network anomalies, when Bloom filters are used for packet forwarding. We found three such anomalies: packet storms, packet loops, and flow duplication. They can severely disrupt the network infrastructure and be used for denial-of-service attacks against the network or target services. These security and reliability problems can be solved by using the combination of three techniques. Cryptographically computed edge pair-labels ensure that an attacker cannot construct Bloom filter-based path identifiers for chosen path. Varying the Bloom filter parameters locally at each router prevents packet storms and using bit permutations on the Bloom filter locally at each router prevent accidental and malicious loops and flow duplications.

This thesis consists of an overview and of the following 8 publications:

  1. Mikko Särelä, Teemu Rinta-aho, Sasu Tarkoma. RTFM: Publish/subscribe internetworking architecture. In ICT Mobile Summit, Accepted as a poster, published on the full paper track, Stockholm, Sweden, June 2008.
  2. Dirk Trossen, Mikko Särelä and Karen Sollins. Arguments for an Information-Centric Internetworking Architecture. ACM SIGCOMM Computer Communication Review, Vol. 40, Issue 2, April 2010.
  3. Jarno Rajahalme, Mikko Särelä, Pekka Nikander, and Sasu Tarkoma. Incentive-Compatible Caching and Peering in Data-Oriented Networks. In ACM ReArch'08 - Re-Architecting the Internet (ReArch'08), Madrid, Spain, December 2008.
  4. Jarno Rajahalme, Mikko Särelä, Kari Visala, Janne Riihijärvi. On Name-Based Inter-Domain Routing. Elsevier Computer Networks, Volume 55, Issue 4, Pages 975-986, Special Issue on Architectures and Protocols for the Future Internet, March 2011.
  5. Christian Esteve Rothenberg, Petri Jokela, Pekka Nikander, Mikko Särelä, and Jukka Ylitalo. Self-routing Denial-of-Service Resistant Capabilities using In-packet Bloom Filters. In European Conference on Computer Network Defence (EC2ND), Milan, Italy, November 2009.
  6. Mikko Särelä, Jörg Ott, Jukka Ylitalo. Fast inter-domain mobility with in-packet Bloom filters. In The 5th ACM International Workshop on Mobility in the Evolving Internet Architecture (Mobiarch), Chicago, IL, USA, September 2010.
  7. Mikko Särelä, Christian Esteve Rothenberg, Tuomas Aura, András Zahemszky, Pekka Nikander, Jörg Ott. Forwarding Anomalies in Bloom Filter Based Multicast. In Proceedings of the 30th IEEE International Conference on Computer Communications (INFOCOM), Shanghai, China, April 2011.
  8. Mikko Särelä, Christian Esteve Rothenberg, András Zahemszky, Pekka Nikander, Jörg Ott. BloomCast: Security in Bloom filter based multicast. In 15th Nordic Conference in Secure IT Systems (Nordsec), Espoo, Finland, October 2010.

Keywords: publish-subscribe, internetworking, multicast, Bloom filters

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

© 2011 Aalto University

Last update 2012-06-05