Towards Accelerating IP Lookups on Commodity PC Routers using Bloom Filter: Proposal of Bloom-Bird
Subject Areas : Network ManagementBahram Bahrambeigy 1 * , Mahmood Ahmadi 2 , mahmood Fazlali 3
1 - Islamic Azad University of Kermanshah
2 - Razi university
3 - Shahid Beheshti University
Keywords: Bird , Bloom Filter , Forwarding Information Base , IPv4 , IPv6 , Open Source Routers,
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.
[1] Y. Zhu, Y. Deng, and Y. Chen, "Hermes: an integrated CPU/GPU microarchitecture for IP routing," presented at the Proceedings of the 48th Design Automation Conference, San Diego, California, 2011.#
[2] S. Han, K. Jang, K. Park, and S. Moon, "PacketShader: a GPU-accelerated software router," ACM SIGCOMM Computer Communication Review, vol. 41, pp. 195-206, 2010.#
[3] BIRD Internet Routing Daemon. Available: http://bird.network.cz#
[4] Quagga Routing Suite. Available: http://www.nongnu.org/quagga/#
[5] M. Handley, O. Hodson, and E. Kohler, "XORP: an open platform for network research," ACM SIGCOMM Computer Communication Review, vol. 33, pp. 53-57, 2003.#
[6] B. H. Bloom, "Space/time trade-offs in hash coding with allowable errors," Communications of the ACM, vol. 13, pp. 422-426, 1970.#
[7] S. Tarkoma, C. E. Rothenberg, and E. Lagerspetz, "Theory and practice of bloom filters for distributed systems," Communications Surveys & Tutorials, IEEE, vol. 14, pp. 131-155, 2012.#
[8] L. Fan, P. Cao, J. Almeida, and A. Z. Broder, "Summary cache: a scalable wide-area web cache sharing protocol," IEEE/ACM Transactions on Networking (TON), vol. 8, pp. 281-293, 2000.#
[9] C. E. Rothenberg, C. A. B. Macapuna, F. L. Verdi, and M. F. Magalhães, "The deletable bloom filter: a new member of the bloom family," IEEE Communications Letters, vol. 14, pp. 557-559, 2010.#
[10] A. Broder and M. Mitzenmacher, "Network Applications of Bloom Filters: A Survey," Internet Mathematics, vol. 1, pp. 636-646, 2002.#
[11] M. Ahmadi and S. Wong, "Modified collision packet classification using counting Bloom filter in tuple space," presented at the Proceedings of the 25th conference on Proceedings of the 25th IASTED International Multi-Conference: parallel and distributed computing and networks, Innsbruck, Austria, 2007.#
[12] L. Hyesook and L. Nara, "Survey and proposal on binary search algorithms for longest prefix match," Communications Surveys & Tutorials, IEEE, vol. 14, pp. 681-697, 2012.#
[13] S. Dharmapurikar, P. Krishnamurthy, and D. E. Taylor, "Longest prefix matching using bloom filters," presented at the Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, Karlsruhe, Germany, 2003.#
[14] S. Sahni and K. S. Kim, "Efficient construction of multibit tries for IP lookup," IEEE/ACM Trans. Netw., vol. 11, pp. 650-662, 2003.#
[15] K. Lim, K. Park, and H. Lim, "Binary search on levels using a Bloom filter for IPv6 address lookup," presented at the Proceedings of the 5th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, Princeton, New Jersey, 2009.#
[16] S. Haoyu, H. Fang, M. Kodialam, and T. V. Lakshman, "IPv6 Lookups using Distributed and Load Balanced Bloom Filters for 100Gbps Core Router Line Cards," in INFOCOM 2009, IEEE, 2009, pp. 2518-2526.#
[17] H. Lee and A. Nakao, "Improving Bloom Filter Forwarding Architectures," IEEE Communications Letters, vol. 18, pp. 1715-1718, 2014.#
[18] H. Lee and A. Nakao, "Improving Routing Table Lookup in Software Routers," IEEE Communications Letters, vol. 19, pp. 957-960, 2015.#
[19] J. Bonwick, "The slab allocator: an object-caching kernel memory allocator," presented at the Proceedings of the USENIX Summer 1994 Technical Conference on USENIX Summer 1994 Technical Conference - Volume 1, Boston, Massachusetts, 1994.#
[20] RouteViews IPv4 BGP RIBs. December 2008, December 2010, July 2013. Available: http://routeviews.org/#
[21] RouteViews IPv6 BGP RIBs. December 2011, December 2012, November 2013. Available: http://routeviews.org/#
[22] ipv6gen, IPv6 prefix generator. Available: https://code.google.com/p/ipv6gen/#