Name
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/IWQoS.2018.8624188 | 2018 IEEE/ACM 26th International Symposium on Quality of Service (IWQoS) |
Keywords | Field | DocType |
OBMA,uninterrupted update processing,route updates,fast incremental updates,storage efficiency,time complexity,commodity CPU,Poptrie,software defined networks,software-based IP route lookup,bitmap data structure minimization | Data structure,Byte,Cache,Computer science,Parallel computing,Real-time computing,Storage efficiency,Bitmap,Time complexity,Memory footprint,Speedup | Conference |
ISSN | ISBN | Citations |
1548-615X | 978-1-5386-2543-9 | 3 |
PageRank | References | Authors |
0.37 | 0 | 9 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chuwen Zhang | 1 | 9 | 3.48 |
| Yong Feng | 2 | 10 | 2.50 |
| Haoyu Song | 3 | 734 | 42.50 |
| Ying Wan | 4 | 11 | 3.52 |
| Wenquan Xu | 5 | 3 | 3.08 |
| Yilun Wang | 6 | 7 | 1.12 |
| Dai Huichen | 7 | 268 | 19.51 |
| Yang Li | 8 | 659 | 125.00 |
| Bin Lin | 9 | 3 | 0.37 |