DOI: 10.3724/SP.J.1016.2011.01611

Chinese Journal of Computers (计算机学报) 2011/34:9 PP.1611-1620

Decomposed Storage Model of FIB for Cluster Router

The fast increasing of FIB has put unprecedented pressure to the Internet routers. The decomposed storage of FIB has theretofore been widely suggested, which explores the balance of storage overhead over routers’line cards. SPAL can achieve the decomposed storage of FIB, but its implement is very complex, and there exists many redundancy storage of FIB. In this paper, we propose a novel decomposed storage model of FIB, DSF(Decomposed Storage of FIB), which can reduce the unnecessary redundancy of FIB storage across line cards. Moreover, we discuss an enhanced mechanism: EDSF. The real-FIB experiments show that EDSF can further minimize the diversity of line cards’storage. The design and the implementation of our proto type is also validated in detail showing that the proposed architecture is compatible with the existing commercial core-routers.

Key words:router,route,FIB,decomposed storage,IP prefix

ReleaseDate:2014-07-21 15:55:26

[1] Meyer D, Zhang L, Fall K. Report from the IAB workshop on routing and addressing. RFC 4984, 2007

[2] Xu Ke, Wu Jian-Ping, Xu Ming-Wei. Advanced Computer Networks: Architecture, Protocol Mechanism, Algorithm Design and Router Technology. Beijing: Mechanism Industry Press, 2009(in Chinese) (徐恪, 吴建平, 徐明伟. 高等计算机网络: 体系结构、协议机制、算法设计与路由器技术. 北京: 机械工业出版社, 2009)

[3] Jiang W, Wang Q, Prasanna V K. Beyond TCAMs: An SRAM-based multi-pipeline architecture for terabit IP lookup//Proceedings of the INFOCOM 2008.Phoenix, USA, 2008: 1786-1794

[4] Akhbarizadeh Mohammad J, Nourani Mehrdad. An IP packet forwarding technique based on partitioned lookup table//Proceedings of the IEEE International Conference on Communications(ICC2002). New York, NY, 2002

[5] Tzeng Nian-Feng. Routing table partitioning for speedy packet lookups in scalable routers. IEEE Transactions on Parallel and Distributed Systems, 2006, 17(5): 481-494

[6] Cisco Systems, Cisco 12016 Gigabit Switch Router, Data Sheet. http: //, 2001

[7] Juniper Networks, Inc. T-Series Routing Platforms: System and Packet Forwarding Architecture. white paper, http: //, Apr. 2002

[8] Hitachi, Ltd. The Hitachi GR2000 Gigabit Router Series. http: //, 2002

[9] Xu Ming-Wei, Xu Ke. Design and implementation of high performance security router BW7000. Engineering Sciences, 2002, 4(3): 54-62(in Chinese) (徐明伟, 徐恪. 高性能安全路由器BW7000的设计与实现. 中国工程科学, 2002, 4(3): 54-62)

[10] Morris R, Kohler E, Jannotti J, Kaashoek M F. The click modular router//Proceedings of the 17th Symposium on Operating Systems Principles (SOSP’99). Kiawah Island, SC, USA, 1999: 217-231