Packet forwarding using improved Bloom filters

Abstract

Efficient IPv6 packet forwarding still is a major bottleneck in todays networks. Especially in the internet core we face very large routing tables and a high number of high-speed links. In addition, economical restrictions exist in terms of manufacturing and operation costs of routers. Resources are limited and network providers reluctantly change their infrastructure.On the other hand the number of internet hosts keeps exploding. Not only PCs and mobile computers, but all kinds of mobile devices want to connect to the internet. With low-cost end-user flatrates the number of households connecting to the net also increases. Economically emerging countries do their share. Unbalanced distribution of IPv4 addresses leads to local service shortages. The address space IPv4 provides is close to getting exhausted.Demand is high for efficient IPv6 packet forwarding mechanisms. In the last few years a lot of work has been done on hash tables and summaries that allow compact representations and constant lookup time. The features sound attractive for IPv6 routing, however, no evaluation exists for tables with millions of entries and no applications are known to make use of the proposed data structures. Furthermore, the structures are usually designed to fit generic applications. A survey and evaluation considering applicability in IPv6 routing seems appropriate. In addition we will explore new ways of exploiting the harsh conditions prevailing in the internet core to design a deployable data structure specialized for IPv6 lookup applications. Our design achieves an improvement in size by the factor of \factor. Moreover, it is easily adjustable to fit different cost functions and the behavior is highly predictable.