OBMA: Minimizing Bitmap Data Structure with Fast and Uninterrupted Update Processing
Authors:
- 1 June 2018
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-6
Abstract
Software-based IP route lookup is one of the key components in Software Defined Networks. To address challenges on density, power and cost, Commodity CPU is preferred over other platforms to run lookup algorithms. As network functions become richer and more dynamic, route updates are more frequent. Unfortunately, previous works put less effort on fast incremental updates. On the other hand, The cache in CPU could be a performance limiter due to its small size, which requires algorithm designers to give high priority on storage efficiency in addition to time complexity. In this paper, we propose a new route lookup algorithm, OBMA, which improves update performance and storage efficiency while maintaining high lookup speed. The extensive experiments over real-word traces show that OBMA reduces the memory footprint to just 4.52 bytes/prefix, supports update speed up to 7.2 M/s which is 12.5 times faster than the state-of-the-art algorithm Poptrie. Besides, OBMA achieves up to 195.87 Mpps lookup speed with a single thread. Tests on comprehensive performance of lookup and update show that OBMA can sustain high lookup speed with update speed increasing.Keywords
This publication has 7 references indexed in Scilit:
- SWIFT2017
- PoptrieACM SIGCOMM Computer Communication Review, 2015
- Guarantee IP lookup performance with FIB explosionACM SIGCOMM Computer Communication Review, 2014
- Fast hash table lookup using extended bloom filterACM SIGCOMM Computer Communication Review, 2005
- Longest prefix matching using bloom filters2003
- Survey and taxonomy of IP address lookup algorithmsIEEE Network, 2001
- Small forwarding tables for fast routing lookupsACM SIGCOMM Computer Communication Review, 1997