Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A splitting-after-merging approach to multi-FIB compression and fast refactoring in virtual routers

  • Published:
Frontiers of Information Technology & Electronic Engineering Aims and scope Submit manuscript

Abstract

Virtual routers are gaining increasing attention in the research field of future networks. As the core network device to achieve network virtualization, virtual routers have multiple virtual instances coexisting on a physical router platform, and each instance retains its own forwarding information base (FIB). Thus, memory scalability suffers from the limited on-chip memory. In this paper, we present a splitting-after-merging approach to compress the FIBs, which not only improves the memory efficiency but also offers an ideal split position to achieve system refactoring. Moreover, we propose an improved strategy to save the time used for system rebuilding to achieve fast refactoring. Experiments with 14 real-world routing data sets show that our approach needs only a unibit trie holding 134 188 nodes, while the original number of nodes is 4 569 133. Moreover, our approach has a good performance in scalability, guaranteeing 90 000 000 prefixes and 65 600 FIBs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Bando, M., Chao, H.J., 2010. FlashTrie: hash-based prefixcompressed trie for IP route lookup beyond 100 Gbps. Proc. IEEE INFOCOM, p.1–9. http://dx.doi.org/10.1109/INFCOM.2010.5462142

    Google Scholar 

  • Bao, J., Chen, Y., Yu, J.S., 2010. A regeneratable dynamic differential evolution algorithm for neural networks with integer weights. J. Zhejiang Univ. Sci. C (Comput. & Electron.), 11(12):939–947. http://dx.doi.org/10.1631/jzus.C1000137

    Article  Google Scholar 

  • Bass, B.M., Calvignac, J.L., Heddes, M.C., et al., 2005. Longest Prefix Match (LPM) Algorithm Implementation for a Network Processor. US Patent 7 383 244.

    Google Scholar 

  • Broder, A., Mitzenmacher, M., 2001. Using multiple hash functions to improve IP lookups. Proc. IEEE INFOCOM, p.1454–1463. http://dx.doi.org/10.1109/INFCOM.2001.916641

    Google Scholar 

  • Chan, C.Y., Ioannidis, Y.E., 1998. Bitmap index design and evaluation. Proc. ACM SIGMOD Int. Conf. on Management of Data, p.355–366. http://dx.doi.org/10.1145/276304.276336

    Google Scholar 

  • Degermark, M., Brodnik, A., Carlsson, S., et al., 1997. Small forwarding tables for fast routing lookups. ACM SIGCOMM Comput. Commun. Rev., 27(4):3–14. http://dx.doi.org/10.1145/263109.263133

    Article  Google Scholar 

  • Eatherton, W.N., Dittia, Z., 2003. Data Structure Using a TREE Bitmap and Method for Rapid Classification of Data in a Database. US Patent 6 728 732.

    Google Scholar 

  • Eatherton, W., Varghese, G., Dittia, Z., 2004. Tree bitmap: hardware/software IP lookups with incremental updates. ACM SIGCOMM Comput. Commun. Rev., 34(2):97–122. http://dx.doi.org/10.1145/997150.997160

    Article  Google Scholar 

  • Fu, J., Rexford, J., 2008. Efficient IP-address lookup with a shared forwarding table for multiple virtual routers. ACM CoNEXT Conf., p.21. http://dx.doi.org/10.1145/1544012.1544033

    Google Scholar 

  • Fu, Z., Wu, S.F., Huang, H., et al., 2001. IPSec/VPN security policy: correctness, conflict detection, and resolution. Proc. Int. Workshop on Policies for Distributed Systems & Networks, p.39–56.

    Chapter  Google Scholar 

  • Han, B., Gopalakrishnan, V., Ji, L.S., et al., 2015. Network function virtualization: challenges and opportunities for innovations. IEEE Commun. Mag., 53(2):90–97. http://dx.doi.org/10.1109/MCOM.2015.7045396

    Article  Google Scholar 

  • Huang, K., Xie, G.G., Li, Y.B., et al., 2011. Offset addressing approach to memory-efficient IP address lookup. Proc. IEEE INFOCOM, p.306–310. http://dx.doi.org/10.1109/INFCOM.2011.5935151

    Google Scholar 

  • Kobayashi, M., Murase, T., Kuriyama, A., 2000. A longest prefix match search engine for multi-gigabit IP processing. IEEE Int. Conf. on Communications, p.1360–1364. http://dx.doi.org/10.1109/ICC.2000.853719

    Google Scholar 

  • Le, H., Ganegedara, T., Prasanna, V.K., 2011. Memoryefficient and scalable virtual routers using FPGA. Proc. 19th ACM/SIGDA Int. Symp. on Field Programmable Gate Arrays, p.257–266.

    Google Scholar 

  • Li, X.L., Wang, H.M., Guo, C.G., et al., 2012. Topology awareness algorithm for virtual network mapping. J. Zhejiang Univ.-Sci. C (Comput. & Electron.), 13(3):178–186. http://dx.doi.org/10.1631/jzus.C1100282

    Article  Google Scholar 

  • Li, Y.B., Zhang, D.F., Huang, K., et al., 2014. A memoryefficient parallel routing lookup model with fast updates. Comput. Commun., 38(1):60–71. http://dx.doi.org/10.1016/j.comcom.2013.10.005

    Article  Google Scholar 

  • Liu, J., Huang, T., Chen, J.Y., et al., 2011. A new algorithm based on the proximity principle for the virtual network embedding problem. J. Zhejiang Univ. Sci. C (Comput. & Electron.), 12(11):910–918. http://dx.doi.org/10.1631/jzus.C1100003

    Article  Google Scholar 

  • Luo, L.Y., Xie, G.G., Salamatian, K., et al., 2013. A trie merging approach with incremental updates for virtual routers. Proc. IEEE INFOCOM, p.1222–1230. http://dx.doi.org/10.1109/INFCOM.2013.6566914

    Google Scholar 

  • McKeown, N., Anderson, T., Balakrishnan, H., et al., 2008. OpenFlow: enabling innovation in campus networks. ACM SIGCOMM Comput. Commun. Rev., 38(2):69–74. http://dx.doi.org/10.1145/1355734.1355746

    Article  Google Scholar 

  • Nilsson, S., Karlsson, G., 1999. IP-address lookup using LCtries. IEEE J. Sel. Areas Commun., 17(6):1083–1092. http://dx.doi.org/10.1109/49.772439

    Article  Google Scholar 

  • Rekhter, Y., Li, T., 1994. A Border Gateway Protocol 4 (BGP-4). RFC 1654, T.J. Watson Research Center & CISCO.

    Book  Google Scholar 

  • Richardson, N.J., Rajgopal, S., Huang, L.B., 2002. Method for Increasing Storage Capacity in a Multi-bit Trie-Based Hardware Storage Engine by Compressing the Representation of Single-Length Prefixes. US Patent 7 162 481.

    Google Scholar 

  • Saravanan, K., Senthilkumar, A., 2015. An efficient parallel prefix matching architecture using Bloom filter for multi-bit trie IP lookup algorithm in FPGA. Optoelectron. Adv. Mat.-Rap. Commun., 9(5):803–807.

    Google Scholar 

  • Sezer, S., Scott-Hayward, S., Chouhan, P.K., et al., 2013. Are we ready for SDN? Implementation challenges for software-defined networks. IEEE Commun. Mag., 51(7):36–43. http://dx.doi.org/10.1109/MCOM.2013.6553676

    Article  Google Scholar 

  • Song, H.Y., Turner, J., Lockwood, J., 2005. Shape shifting tries for faster IP route lookup. IEEE Int. Conf. on Network Protocols, p.358–367. http://dx.doi.org/10.1109/ICNP.2005.36

    Google Scholar 

  • Song, H.Y., Kodialam, M., Hao, F., et al., 2009. Scalable IP lookups using shape graphs. 17th IEEE Int. Conf. on Network Protocols, p.73–82. http://dx.doi.org/10.1109/ICNP.2009.5339697

    Google Scholar 

  • Song, H.Y., Kodialam, M., Hao, F., et al., 2010. Building scalable virtual routers with trie braiding. Proc. IEEE INFOCOM, p.1–9. http://dx.doi.org/10.1109/INFCOM.2010.5461960

    Google Scholar 

  • Song, H.Y., Kodialam, M., Hao, F., et al., 2012. Efficient trie braiding in scalable virtual routers. IEEE/ACM Trans. Netw., 20(5):1489–1500. http://dx.doi.org/10.1109/TNET.2011.2181412

    Article  Google Scholar 

  • Srinivasan, V., Varghese, G., 1999. Fast address lookups using controlled prefix expansion. ACM Trans. Comput. Syst., 17(1):1–40. http://dx.doi.org/10.1145/296502.296503

    Article  Google Scholar 

  • Wang, Z., Chen, H.F., Xie, L., et al., 2010. Retransmission in the network-coding-based packet network. J. Zhejiang Univ.-Sci. C (Comput. & Electron.), 11(7):544–554. http://dx.doi.org/10.1631/jzus.C0910475

    Article  Google Scholar 

  • Wu, K.S., Otoo, E.J., Shoshani, A., 2006. Optimizing bitmap indices with efficient compression. ACM Trans. Database Syst., 31(1):1–38. http://dx.doi.org/10.1145/1132863.1132864

    Article  Google Scholar 

  • Xie, G.G., He, P., Guan, H.T., et al., 2011. PEARL: a programmable virtual router platform. IEEE Commun. Mag., 49(7):71–77. http://dx.doi.org/10.1109/MCOM.2011.5936157

    Article  Google Scholar 

  • Yu, H., Mahapatra, R., Bhuyan, L., 2009. A hash-based scalable IP lookup using Bloom and fingerprint filters. Proc. 17th IEEE Int. Conf. on Network Protocols, p.264–273. http://dx.doi.org/10.1109/ICNP.2009.5339676

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. College of Computer Science and Electronic Engineering, Hunan University, Changsha, 410082, China

    Da-fang Zhang, Dan Chen, Yan-biao Li, Kun Xie & Tong Shen

  2. Department of Electrical and Computer Engineering, State University of New York, New York, 11790, USA

    Kun Xie

Authors
  1. Da-fang Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dan Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yan-biao Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Kun Xie
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Tong Shen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Da-fang Zhang or Dan Chen.

Additional information

Project supported by the National Basic Research Program (973) of China (No. 2012CB315805), the National Natural Science Foundation of China (Nos. 61173167 and 61472130), the Prospective Research Project on Future Networks of Jiangsu Future Networks Innovation Institute, China (No. 2013095-1-05), the Hunan Provincial Innovation Foundation for Postgraduate, China (No. CX2014B150), and the State Scholarship Fund of China (No. 201406130048)

ORCID: Dan CHEN, http://orcid.org/0000-0001-7049-9945

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhang, Df., Chen, D., Li, Yb. et al. A splitting-after-merging approach to multi-FIB compression and fast refactoring in virtual routers. Frontiers Inf Technol Electronic Eng 17, 1266–1274 (2016). https://doi.org/10.1631/FITEE.1500499

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1631/FITEE.1500499

Key words

CLC number

Search

Navigation