State-Efficient Forwarding with In-packet Bloom Filters

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
School of Electrical Engineering | Doctoral thesis (article-based) | Defence date: 2017-06-14
Date
2017
Major/Subject
Mcode
Degree programme
Language
en
Pages
120 + app. 64
Series
Aalto University publication series DOCTORAL DISSERTATIONS, 108/2017
Abstract
The Internet Protocol (IP) has been the dominant packet forwarding mechanism in the Internet during the past decades. Despite of its merits, IP suffers from known shortcomings, such as ever expanding routing tables on network routers, limited support for multicast, and attacks that utilize destination address-based routing.  In this dissertation, we introduce a new packet forwarding mechanism that is not based on a global addressing scheme. In this solution, packet forwarding is based on strict source-routing. The calculated path from the sender to the receiver is encoded in a space-efficient Bloom filter, that is inserted in the packet header, and each router on the path can effiently verify the outgoing links where the packet should be delivered to.  Bloom filter-based forwarding has some advantages over IP forwarding. First, with Bloom filter forwarding, network routers do not need to maintain any routing table to make the forwarding decision for packets. Instead, the router verifies which of its interfaces have been included in the Bloom filter and forwards the packet out from matching interfaces. Second, the simplicity in Bloom filter verification allows a very efficient packet forwarding decision in a router. Finally, the Bloom filter forwarding offers a native multicast support without additional state in network routers.  A disadvantage of Bloom filter is that the verification may provide false positive results. With Bloom filter forwarding this means that sometimes additional packets are delivered over links that do not belong to the original path. We discuss this downside, verify the actual effects of false positives on forwarding decisions, and suggest potential solutions to overcome the problem.  Deploying a new forwarding mechanism is challenging because IP has a firm position in the Internet. We discuss about two potential deployment scenarios, where we show that Bloom filter-based forwarding can be deployed also in partial networks, replacing IP-based routing and multicast to enable more efficient networking.

Viimeisten vuosikymmenien aikana IP on ollut hallitseva liikenteen välitysmenetelmä Internetissä. Huolimatta hyödyistään, IP kärsii tietyistä ongelmista kuten jatkuvasti kasvavista reititystauluista reitittimissä, rajoitetusta monilähetyksen tuesta sekä hyökkäyksistä, jotka käyttävät hyväkseen kohdeosoiteperusteista reititystä.  Tässä väitöskirjassa me esittelemme uuden lähdereititykseen pohjautuvan liikenteenvälitysmenetelmän, joka ei käytä maailmanlaajuista osoitteistusta. Etukäteen laskettu polku lähettäjältä vastaanottajalle lisätään tilankäytöltään tehokkaaseen Bloom-suodattimeen, joka vuorostaan sijoitetaan lähetettävän paketin otsakkeeseen. Verkon reitittimet tarkistavat paketin suotimesta onko jokin niiden ulospäin lähtevistä rajapinnoista sisällytetty suotimeen, ja lähettävät paketin ulos sisällytetyistä rajapinnoista.  Bloom-suodattimeen perustuvalla pakettien välityksellä on eräitä etuja IP-pohjaiseen välitykseen nähden. Ensinnäkin reitittimien ei tarvitse pitää yllä reititystauluja koska pakettien välitys perustuu rajapintojen identiteettien tarkistamiseen Bloom-suodattimesta. Toiseksi identiteetin tarkistaminen Bloom-suodattimesta on hyvin yksinkertainen toimenpide, ja se mahdollistaa erittäin nopean välityspäätöksen tekemisen reittimessä. Lopuksi Bloom-suodattimeen perustuva reititys mahdollistaa luontaisen monilähetyksen ilman ylimääräistä tilatietoa verkon reittimissä. Bloom-suodattimiin perustuvissa järjestelmissä on myös haittapuolensa. Yksittäisen alkion tarkastaminen suodattimesta saattaa aiheuttaa virheellisen positiivisen vastauksen. Pakettien välityksessä tämä tarkoittaa ylimääräisen paketin kopion lähettämistä alkuperäiseen polkuun kuulumattomalle yhteydelle. Keskustelemme tästä haittapuolesta, todennamme sen haitat välityspäätöksen teossa ja ehdotamme mahdollisia ratkaisuja ongelman ratkaisuun.  Uuden välitysjärjestelmän käyttöönotto on haastavaa, koska IP:llä on hyvin vahva asema Internetissä. Keskustelemme kahdesta erilaisesta käyttöönottomahdollisuudesta ja näytämme, että Bloom-suodattimeen perustuva välitys voidaan ottaa käyttöön myös rajoitetuissa osissa Internetiä, korvaten IP-pohjaisen välityksen ja monilähetyksen, mahdollistaen tehokkaamman liikenteen välityksen.
Description
Supervising professor
Ott, Jörg, Prof., Aalto University, Department of Communications and Networking, Finland
Keywords
bloom filters, multicast, forwarding, bloom-suodattimet, monilähetys, liikenteenvälitys
Other note
Parts
  • [Publication 1]: P. Jokela, A. Zahemszky, C. Esteve Rothenberg, S. Arianfar, P. Nikander. LIPSIN: Line-Speed Publish/Subscribe Inter-Networking. In Proc. of the ACM SIGCOMM 2009, Barcelona, Spain, August 2009.
    DOI: 10.1145/1594977.1592592 View at publisher
  • [Publication 2]: J. Keinänen, P. Jokela, K. Slavov. Implementing zFilter based forwarding node on a NetFPGA. In NetFPGA Developers Workshop, Stanford, CA, August 2009.
  • [Publication 3]: C. Esteve Rothenberg, P. Jokela, P. Nikander, M. Särelä, J. Ylitalo. Self-routing Denial-of-Service Resistant Capabilities using In-packet Bloom Filters. In Proc. of the European Conference on Computer Network Defense, EC2ND’09, Milan, Italy, November 2009.
    DOI: 10.1109/EC2ND.2009.14 View at publisher
  • [Publication 4]: A. Zahemszky, P. Jokela, M. Särelä, S. Ruponen, J. Kempf, P. Nikander. MPSS: Multiprotocol Stateless Switching. In Proc. of the 13th IEEE Global Internet Symposium 2010, San Diego, CA, USA, March 2010.
    DOI: 10.1109/INFCOMW.2010.5466670 View at publisher
  • [Publication 5]: A. Zahemszky, P. Jokela, T. Jokikyyny. Autonomicity in Virtual Private Network Provisioning for Enterprises. In Proc. of the IEEE International Workshop on Management of Emerging Networks and Services (IEEE MENS), Miami, Florida, USA, December 2010.
    DOI: 10.1109/GLOCOMW.2010.5700395 View at publisher
  • [Publication 6]: P. Jokela, H. Mahkonen, C. Esteve Rothenberg, J. Ott. (Deployable) Reduction of Multicast State with In-packet Bloom Filters. In Proc. of the IFIP Networking 2013, New York, May 2013.
Citation