State-Efficient Forwarding with In-packet Bloom Filters

Petri Laari

Research output: ThesisDoctoral ThesisCollection of Articles

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.
Translated title of the contributionBloom-suodattimiin pohjautuva vähätilainen liikenteenvälitysjärjestelmä
Original languageEnglish
QualificationDoctor's degree
Awarding Institution
  • Aalto University
Supervisors/Advisors
  • Ott, Jörg, Supervising Professor
Publisher
Print ISBNs978-952-60-7470-2
Electronic ISBNs978-952-60-7469-6
Publication statusPublished - 2017
MoE publication typeG5 Doctoral dissertation (article)

Keywords

  • bloom filters
  • multicast
  • forwarding

Fingerprint Dive into the research topics of 'State-Efficient Forwarding with In-packet Bloom Filters'. Together they form a unique fingerprint.

Cite this