并行多流水绿色路由查找架构和算法

doi:10.3969/j.issn.1001-2400.2012.02.024

Abstract

Abstract:

With the development of the next generation internet, the existing router architecture faces many problems,such as performance,complexity and power consumption. With the increase of the network size, how to implement a low-power MSF for IP lookup is a challenge in green and high-performance router designing. This paper represents an FIB multi-level mapping parallel multi-pipeline routing lookup architecture(FMML), with a dynamic routing table mapping algorithm designed to determine the optimal strides for building tree bitmap tries. Finally, experiments using real-life routing tables demonstrate that our solution can reduce 30％ power consumption of routing lookup.

Key words: routing lookup, low power, multi-pipeline, green router, dynamic mapping

CLC Number:

TP393

YUAN Bo;WANG Binqiang;WANG Zhiming. Green IP lookup architecture and algorithm based on the parallel multi-pipeline[J].J4, 2012, 39(2): 145-152+167.

References

［1］ Eatherton W, Varghese G, Dittia Z. Tree Bitmap: Hardware/Software IP Lookups with Incremental Updates［J］. SIGCOMM Comput Commun Rev, 2004, 34(2): 97-122.
［2］ Jiang W, Wang Q, Prasanna V K. Beyond TCAMs: an SRAM Based Parallel Multi-pipeline Architecture for Terabit IP Lookup［C］//Proc INFOCOM. Phoenix: IEEE, 2008: 1786-1794.
［3］ Taylor D E. Survey and Taxonomy of Packet Classification Techniques［J］. ACM Comput Surv, 2005, 37(3): 238-275.
［4］ Gupta M, Singh S. Greening of the Internet［C］//Proc SIGCOMM. New York: ACM, 2003: 19-26.
［5］ Lyons A M, Neilson D T, Salamon T R. Energy Efficient Strategies for High Density Telecom Applications［R］. Princeton: Princeton University, 2008.
［6］ Chabarek J, Sommers J, Barford P, et al. Power Awareness in Network Design and Routing［C］//Proc INFOCOM. Phoenix: IEEE, 2008: 457-465.
［7］ Mandviwalla M, Tzeng N F. Energy-efficient Scheme for Multiprocessor-based Router Linecards［C］//Proc SAINT. Phoenix: IEEE, 2006: 155-163.
［8］ Nedevschi S, Popa L, Iannaccone G, et al. Reducing Network Energy Consumption Via Sleeping and Rateadaptation［C］//NSDI. San Francisco: IEEE, 2008: 323-336.
［9］ Carli L D, Pan Y, Kumar A, et al. Flexible Lookup Modules for Rapid Deployment of New Protocols in High-speed Routers［C］//Proc SIGCOMM. New York: ACM, 2009: 207-218.
［10］ Song H, Turner J, Lockwood J. Shape Shifting Trie for Faster IP Router Lookup［C］//Proc ICNP. San Francisco: IEEE, 2005: 358-367.
［11］ Sahni S, Kim K S. Efficient Construction of Multibit tries for IP Lookup［J］. IEEE/ACM Trans on Netw, 2003, 11(4): 650-662.
［12］ Wu Chunming, Wang B Q. On the Design of Green Reconfigurable Router towards Energy Efficient Internet［C］//Proc IEEE GreenComm'09. Dresden: IEEE, 2009: 83-87.
［13］ Zheng K, Hu C, Lu H, et al. A TCAM-based Distributed Parallel IP Lookup Scheme and Performance Analysis［J］. IEEE/ACM Trans on Netw, 2006, 14(4): 863-875.
［14］ Jiang W, Prasanna V K. Towards Green Routers: Depth-bounded Multi-pipeline Architecture for Power-efficient IP Lookup［C］//Proc IPCCC. San Jose: ACM, 2008: 185-192.
［15］ Kaxiras S, Keramidas G. IP Stash: a Set-associative Memory Approach for Efficient IP-lookup［C］//INFOCOM. Miami: IEEE, 2005: 992-1001.
［16］ Luo Y, Yu J, Yang J, et al. Conserving Network Processor Power Consumption by Exploiting Traffic Variability［J］. ACM Trans on Archit Code Optim, 2007, 4(1): 4.
［17］ Jiang W, Prasanna V K. Reducing Dynamic Power Dissipation in Pipelined Forwarding Engines［C］//Proc ICCD. Lake Tahoe: IEEE, 2009: 144-149.
［18］ Kennedy A, Wang X, Liu Z, et al. Low Power Architecture for High Speed Packet Classification［C］//Proc ANCS. San Jose: ACM, 2008: 131-140.
［19］ Hasan J, Vijaykumar T N. Dynamic Pipelining: Making IP-lookup Truly Scalable［C］//Proc SIGCOMM. Philadelphia: ACM, 2005: 205-216.
［20］ Kumar S, Becchi M, Crowley P, et al. CAMP: Fast and Efficient IP Lookup Architecture［C］//Proc ANCS. San Jose: ACM, 2006: 51-60.
［21］ Liang X, Turgay K, Brooks D. Architectural Power Models for SRAM and CAM Structures Based on Hybrid Analytical/Empirical Techniques［C］//Proc ICCAD. San Jose: IEEE, 2007: 824-830.
［22］ Do M Q, Drazdziulis M, Larsson-Edefors P, et al. Parameterizable Architecture-level SRAM Power Model Using Circuitsimulation Backend for Leakage Calibration［C］//Proc ISQED. San Jose: IEEE, 2006: 557-563.
［23］ Thoziyoor S, Ahn J H, Monchiero M, et al. A Comprehensive Memory Modeling Tool and Its Application to the Design and Analysis of Future Memory Hierarchies［C］//Proc ISCA. Beijing: IEEE, 2008: 51-62.
［24］ RIPE. RIS Raw Data. ［DB/OL］. ［2008-05-07］. http://data.ris.ripe.net.
［25］ Zane F, Narlikar G J, Basu A. CoolCAMs: Power-efficient TCAMs for Forwarding Engines［C］//Proc INFOCOM. San Francisco: IEEE, 2003: 42-52.

[1]	ZHAO Hui,FENG Nanzhi,WANG Quan,WAN Bo,WANG Jing. Dynamic semi-online task scheduling method for the edge computing platform [J]. Journal of Xidian University, 2021, 48(6): 8-15.
[2]	CHEN Diping, YING Tao, DONG Gang. Design of a low-power low-temperature-drift LDO regulator in mobile chips [J]. Journal of Xidian University, 2018, 45(6): 57-62.
[3]	CHEN Zhenhai, WEI Jinghe, YU Zongguang, SU Xiaobo, XUE Yan, ZHANG Hong. High precision common mode charge error fore-ground calibration circuit for the charge-domain ADC [J]. Journal of Xidian University, 2018, 45(6): 137-143+149.
[4]	CAI Jiangzheng;HEI Yong;YUAN Jia;CHEN Liming. Near-threshold non-precharged SRAM [J]. Journal of Xidian University, 2018, 45(1): 106-111.
[5]	MENG Fanzhen;LIU Hong;WANG Mingliang;LIN Shuiyang;TIAN Tong. Design of the CMOS low power sub-sampler with integrated filtering for the internet of things [J]. Journal of Xidian University, 2017, 44(3): 108-113.
[6]	MENG Fanzhen;LIU Hong;WANG Mingliang;LIN Shuiyang;TIAN Tong. Design of the low power wake-up receiver for internet of things communication [J]. Journal of Xidian University, 2017, 44(2): 95-100.
[7]	TANG Weitong;WANG Pengjun;WANG Qian. Design of the magnitude ternary comparator of CNFET [J]. J4, 2016, 43(1): 139-143+156.
[8]	ZHANG Yimeng;ZHANG Yuming;ZHANG Yimen. Low power dissipation real time counter for sensor network application [J]. J4, 2015, 42(6): 66-69+112.
[9]	ZHANG Li;ZHUANG Yiqi;ZHAO Weisheng;TANG Hualian. Design of the writing circuit with a low supply voltage for the spin-transfer torque random access memory [J]. J4, 2014, 41(3): 131-137.
[10]	DU Yongqian;ZHUANG Yiqi;LI Xiaoming;JING Xin;DAI Li. New type bandgap reference for UHF RFID tag [J]. J4, 2013, 40(2): 148-152+200.
[11]	TANG Longfei;ZHUANG Yiqi;LIU Weifeng;JIN Zhao. Low-power BLF genarator for the UHF RFID tag [J]. J4, 2011, 38(5): 152-158+164.
[12]	ZHU Qi-xi;CHE De-liang;SHEN Xu-bang. Design of a low power MCU used for no-magnetic flow measurement [J]. J4, 2010, 37(5): 921-926.
[13]	SUN Qiang;SUN Xing-qi;MA Guang-sheng. High-level power optimization method for multiple supply voltage using the multi-objective genetic algorithm [J]. J4, 2009, 36(5): 933-939.
[14]	LIU Feng;ZHUANG Yi-qi;DAI Guo-ding. Algorithm and VLSI architecture for computational complexity scalable block marching motion estimation [J]. J4, 2005, 32(6): 901-906.
[15]	ZHU Zhang-ming;YANG Yin-tang. A sub-１V PTAT voltage reference based on the bulk-driven technique [J]. J4, 2005, 32(3): 367-369.

Green IP lookup architecture and algorithm based on the parallel multi-pipeline

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 10