BUFFALO: Bloom Filter Forwarding Architecture for Large Organizations / Accountability in Hosted Virtual Networks

BUFFALO: Bloom Filter Forwarding Architecture for Large Organizations; Minlan Yu

In enterprise and data center networks, the scalability of the data plane becomes increasingly challenging as forwarding tables and link speeds grow. Simply building switches with larger amounts of faster memory is not appealing, since high-speed memory is both expensive and power hungry. Implementing hash tables in SRAM is not appealing either because it requires significant overprovisioning to ensure that all forwarding table entries fit. Instead, we propose the BUFFALO architecture, which uses a small SRAM to store one Bloom filter of the addresses associated with each outgoing link. We provide a practical switch design leveraging two unique features of enterprise and data center networks: flat addresses and shortest-path routing. BUFFALO gracefully handles false positives without reducing the packet-forwarding rate, while guaranteeing that packets reach their destinations with bounded stretch. We tune the sizes of Bloom filters to minimize false positives for a given memory size. We also handle routing changes and dynamically adjust Bloom filter sizes using counting Bloom filters in slow memory. Our extensive analysis, simulation and prototype implementation in kernel-level Click show that BUFFALO significantly reduces memory cost, increases the scalability of the data plane, and improves packet-forwarding performance.

Accountability in Hosted Virtual Networks; Eric Keller

Virtualization enables multiple networks, each customized for a particular purpose, to run concurrently over a shared substrate. One such model for managing these virtual networks is to create a hosting platform where companies can deploy services by leasing a portion of several physical routers. While lowering the barrier for innovation in the network, this model introduces new security concerns. In this paper we examine the issue of accountability in this setting of hosted virtual networks. That is, how a service provider can know its software is running without modification and that the infrastructure provider’s physical router is forwarding packets as instructed with the quality of service promised. Rather than presenting a single specification of what every router on the Internet must look like, in this paper we examine two possible approaches: one that detects violations by monitoring the service and one that prevents violations from occurring in the first place. For each, we provide a description of an architecture that can be achieved with technology available today, the limitations of that architecture, and then propose an extension which overcomes the limitations.

Speaker Details

Eric Keller is a 4th year Ph.D. student in the Electrical Engineering department at Princeton University where he is actively working on network virtualization. Prior to Princeton, Eric received a B.S. in Computer Engineering from Virginia Tech and then spent 7 years at Xilinx exploring various applications and tools to exploit the flexibility and re-programmability of FPGAs.

Minlan Yu is a 4th year Ph.D. student in the computer science department at Princeton University. She received her B.A. in computer science and mathematics from Peking University in 2006 and her M.A. in computer science from Princeton University in 2008. She has interned at AT&T Labs Research and Bell Labs. Her research interest is in network virtualization, enterprise and data center networks.

Date:
Speakers:
Eric Keller and Minlan Yu
Affiliation:
Princeton University