BloomCasting for publish/subscribe networks
Loading...
Journal Title
Journal ISSN
Volume Title
Sähkötekniikan korkeakoulu |
Doctoral thesis (article-based)
Checking the digitized thesis and permission for publishing
Instructions for the author
Instructions for the author
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Author
Date
2011
Major/Subject
Mcode
Degree programme
Language
en
Pages
79, [77] s. : kuv. ; 25 cm.
Series
Aalto University publication series.
Doctoral dissertations,
49/2011
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.Yksi Internetin puutteista on se, ettei ole mitään kaikille sovelluksille yhteistä tapaa nimetä informaatiota. Julkaisija/tilaaja-malli on yksi ehdotus, jolla Internet-arkkitehtuuria voisi muuttaa tämän puutteen korvaamiseksi. Väitöskirjassani kehitän julkaisija/tilaaja-malliin pohjautuvan verkkoarkkitehtuurin, joka pohjautuu työlleni PSRIP-projektissa. Arkkitehtuuri koostuu kohtaamisjärjestelmästä, joka yhdistää julkaisijat ja tilaajat, ja Bloom-suodattimiin pohjautuvasta monen vastaanottajan viestintäkanavasta, jolla julkaistu sisältö toimitetaan tilaajille. Internetin kattavalla kohtaamisjärjestelmällä on korkeat vaatimukset. Tutkin kahta erilaista menetelmää: paikallisiin reitityspolitiikoihin pohjautuvaa järjestelmää ja toinen hajautettuihin hajautustauluihin pohjautuvaa järjestelmää. Ensimmäisen haasteena on skaalautuvuus erityisesti silloin, kun kaikki Internetin verkot eivät osallistu järjestelmän ylläpitoon. Jälkimmäinen on ongelmallinen, sillä siihen pohjautuvat järjestelmät eivät voi taata, mitä reittiä julkaisu ja tilaus -viestit kulkevat järjestelmässä. Näin viesti saattaa kulkea myös julkaisijan tai tilaajan kilpailijan verkon kautta. Ehdotan väitöskirjassani menetelmää, joka yhdistää reunoilla politiikkaan pohjautuvan julkaisu/tilaaja reitityksen ja verkon keskellä yhdistää nämä erilliset saarekkeet hierarkista hajautettua hajautustaulua hyödyntäen. Julkaisujen toimittamiseen tilaajille käytän Bloom-suodattimiin pohjautuvaa järjestelmää. Osoitan väitöskirjassani, että Bloom-suodattimien käyttö pakettien reitittämiseen voi aiheuttaa verkossa merkittäviä vikatilanteita, esimerkiksi pakettiräjähdyksen, silmukan, tai samaan vuohon kuuluvien pakettien moninkertaistumisen. Nämä ongelmat aiheuttavat verkolle turvallisuus- ja luotettavuusongelmia, jotka voidaan ratkaista kolmen tekniikan yhdistelmällä. Ensinnäkin, Bloom-suodattimiin laitettavat polun osia merkitsevät nimet lasketaan kryptografiaa hyödyntäen, ettei hyökkääjä kykene laskemaan Bloom-suodatinta haluamalleen polulle ilman verkon apua. Toisekseen, reitittimet määrittävät Bloom suodatinparametrit paikallisesti siten, ettei pakkettiräjähdyksiä tapahdu. Kolmannekseen, kukin reititin uudelleen järjestelee Bloom-suodattimen bitit varmistaen, ettei suodatin ole enää sama, jos paketti kulkee esimerkiksi silmukan läpi ja palaa samalle takaisin samalle reitittimelle.Description
Supervising professor
Ott, Görg, Prof.Thesis advisor
Nikander, Pekka, Dr.Schultz, Göran, Dr.
Keywords
publish-subscribe, internetworking, multicast, Bloom filters
Parts
- [Publication 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.
- [Publication 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.
- [Publication 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.
- [Publication 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.
- [Publication 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.
- [Publication 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.
- [Publication 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.
- [Publication 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.
