Towards Accelerating IP Lookups on Commodity PC Routers using Bloom Filter: Proposal of Bloom-Bird
Journal Title: Journal of Information Systems and Telecommunication - Year 2017, Vol 5, Issue 1
Abstract
Nowadays, routers are the main backbone of computer networks specifically the Internet. Moreover, the need for high-performance and high-speed routers has become a fundamental issue due to significant growth of information exchange through the Internet and intranets. On the other hand, flexibility and configurability behind the open-source routers has extended their usage via the networks. Furthermore, after assigning the last remaining IPv4 address block in 2011, development and improvement of IPv6-enabled routers especially the open-sources has become one of the first priorities for network programmers and researchers. In IPv6 because of its 128-bits address space compared to 32-bits in IPv4, much more space and time are required to be stored and searched that might cause a speed bottleneck in lookup of routing tables. Therefore, in this paper, Bird as an example of existing open source router which supports both IPv4 and IPv6 addresses is selected and Bloom-Bird (our improved version of Bird) is proposed which uses an extra stage for its IP lookups using Bloom filter to accelerate IP lookup mechanism. Based on the best of our knowledge this is the first application of Bloom filter on Bird software router. Moreover, false positive errors are handled in an acceptable rate because Bloom-Bird scales its Bloom filter capacity. The Bloom-Bird using real-world IP prefixes and huge number of inserted prefixes into its internal FIB (Forwarding Information Base), shows up to 61% and 56% speedup for IPv4 and IPv6 lookups over standard Bird, respectively. Moreover, using manually generated prefix sets in the best case, up to 93% speedup is gained.
Authors and Affiliations
Bahram Bahrambeigy, Mahmood Ahmadi
Keywords
Related Articles
- EP ID EP183851
- DOI -
- Views 156
- Downloads 0
An Improved Method for TOA Estimation in TH-UWB System considering Multipath Effects and Interference
UWB ranging is usually based on the time-of-arrival (TOA) estimation of the first path. There are two major challenges in TOA estimation. One challenge is to deal with multipath channel, especially in indoor environments...
Mitosis detection in breast cancer histological images based on texture features using AdaBoost
Counting mitotic figures present in tissue samples from a patient with cancer, plays a crucial role in assessing the patient’s survival chances. In clinical practice, mitotic cells are counted manually by pathologists in...
Theory and Experiment of Parasitic Element Effects on Spherical Probe-Fed Antenna
Theory and experiment of a spherical probe-fed conformal antenna with a parasitic element mounted on a spherical multilayer structure are presented in this paper. Rigorous mathematical Method of Moments (MoMs) for analyz...
The Surfer Model with a Hybrid Approach to Ranking the Web Pages
Users who seek results pertaining to their queries are at the first place. To meet users’ needs, thousands of webpages must be ranked. This requires an efficient algorithm to place the relevant webpages at first ranks. R...
Lifetime Maximization by Dynamic Threshold and Sensor Selection in Multi-Channel Cognitive Sensor Network
The tiny and low-cost sensors cannot simultaneously sense more than one channel since they do not have high-speed Analog-to-Digital-Convertors (ADCs) and high-power batteries. It is a critical problem when they are used...