A Concise Forwarding Information Base for Scalable and Fast Name Lookups
Loading...
Date
2017-11-30
Journal Title
Journal ISSN
Volume Title
Publisher
IEEE
Abstract
Forwarding information base (FIB) scalability and
its lookup speed are fundamental problems of numerous net-
work technologies that uses location-independent network names.
In this paper we present a new network algorithm, Othello
Hashing, and its application of a FIB design called Concise,
which uses very little memory to support ultra-fast lookups
of network names. Othello Hashing and Concise make use
of minimal perfect hashing and relies on the programmable
network framework to support dynamic updates. Our conceptual
contribution of Concise is to optimize the memory efficiency
and query speed in the data plane and move the relatively
complex construction and update components to the resource-
rich control plane. We implemented Concise on three platforms.
Experimental results show that Concise uses significantly smaller
memory to achieve much faster query speed compared to existing
solutions of network name lookups.
Description
Keywords
SDN, Forwarding, Hashing, Dynamic FIB, Random Graphs