摘要
IP路由器(Internet Protocol Router)是Internet的核心设备。随着Internet的飞速发展，IP路由器在性能和扩展性等方面面临严峻的挑战，其相关研究也受到了广泛的关注。另一方面，当前超大规模集成电路技术快速发展，基于系统芯片(SoC, Systemon Chip)可以进一步提高系统的集成度和系统性能，降低系统功耗等，为电子信息系统的设计和实现提供了新的思路。IP路由器SoC就是采用系统芯片的设计方法，实现IP路由器核心功能的单芯片集成，将系统芯片技术和IP路由器技术相结合，从而有效解决IP路由器的性能、功耗及扩展性等问题。
本文针对IP路由器SoC的关键问题进行了深入的分析，对IP路由器SoC所涉及的IP路由器SoC体系结构、IP路由器SoC片内通信、高性能IP地址查找以及IP路由器SoC的功能验证等关键技术进行了深入研究，提出了一些解决IP路由器SoC关键问题的新方法，并通过系统级建模和软硬件仿真等对提出的方法进行了验证。
论文的主要研究内容和创新性成果包括：
1.基于片上网络(NoC, Network on Chip)技术，对IP路由器SoC的片内通信机制进行了深入的研究。提出了2D-Torus网络中虚通道负载均衡的路由算法(VCLBR,Virtual Channel Load-Balanced Routing algorithm)。该算法从虚通道的层次上进行负载均衡的研究，通过引入随机因子，在保证物理链路负载均衡的情况下，将网络负载均衡地分配到各个虚通道上。实验结果表明，针对不同的流量模型，通过合理选择随机因子的取值，均可明显改善2D-Torus网络的通信性能。
2.在IP路由器SoC片内通信机制的研究中，提出了一种规则的、对称的片上网络拓扑结构，即SD-Torus (Semi-Diagonal Torus)网络。分析了其拓扑性质，并提出了SD-Torus网络中负载均衡的路由算法。实验结果表明，同DMesh、DTorus以及Xmesh网络相比，在相同的实现代价下，SD-Torus网络具有更优的通信性能，便于实现IP路由器SoC中的分布式地址查找和分组交换。
3.对当前IP地址查找技术面临的挑战及并行IP地址查找结构进行了深入的分析和总结，并在此基础上，提出了基于Hash和树位图(Tree-bitmap)的两级IP地址查找结构，该结构充分利用了路由表中前缀长度的分布规律，将基于前缀长度的二分查找技术与树位图(Tree-bitmap)查找技术结合起来，从而实现了高效的IP地址查找。同时，提出了基于SD-Torus网络的并行IP地址查找结构及其算法，该结构按照“临近存储”原则进行路由表的划分和映射，满足在任何节点及其邻居节点上的路由子表可以构成一份完整的路由表，从而降低了分布式地址查找的通信延迟、减少了路由表的存储代价，提高了IP地址查找结构的性能和扩展性。
4.基于大规模并行处理(MPP, Massively Parallel Processing)思想，提出了一种IP路由器SoC的体系结构，该结构中采用大量的、同构的处理单元完成路由器中的转发和交换功能，并使用SD-Torus网络进行片内互连，实现了分布式转发和分布式交换，是一种典型的大规模并行处理的系统芯片结构(MPPSoC)。实验结果表明，该结构具有良好的系统性能和扩展性。
5.设计并实现了一种通用的IP路由器SoC的功能验证平台。该功能验证平台基于自动检查机制，以FPGA为硬件设施，并通过其软件部分进行动态的系统配置，从而实现了不同IP路由器SoC系统的功能验证。该平台充分利用了软件验证的灵活性和FPGA验证的高效性，提高了IP路由器SoC功能验证的效率。
As the core device of the Internet, the Internet protocol (IP) router plays a veryimportant role in the Internet. With the rapid development of the Internet, the IP routeris facing serious challenges in its performance, scalability and power consumption, etc.On the other hand, with the maturity of the very large scale integrated (VLSI) circuittechnology, system on chip (SoC) provides a new solution to the electronic informationsystems, by providing higher system integration, improved system performance, andreduced power consumption. The design and implementation of the IP router SoC is acombination of the IP router technology and the SoC technology, by integrating the corefunctional modules of the IP router system into a single chip, and consequently providehigher performance and scalability.
Based on the extensive analysis and research on the key problems of the IP routerSoC, some new solutions to the IP router SoC design are proposed in this paper. Theresearch mainly focuses on the IP router SoC architecture, the on-chip communicationstechniques, high performance IP address lookup architecture, and the functionalverification of the IP router SoC, etc. The proposed solutions had been validated bymodel-simulation, the software and hardware verification platforms.
The major contributions of this dissertation are as follows.
1. Based on the network on chip (NoC), the communication mechanism in IProuter SoC is studied. A virtual channel load-balanced routing (VCLBR) algorithm for2D-Torus networks is proposed, in which, the traffic load is distributed to the virtualchannels by adopting a random parameter. Simulation results show that compared withthe negative first for Torus networks (NF-T) algorithm, the network performance can bedramatically improved for different traffic pattern by selecting a specific value of therandom parameter respectively.
2. A regular and symmetrical NoC topology, the semi-diagonal Torus (SD-Torus)network is proposed; with its topological properties and a load-balanced routingalgorithm are discussed. Simulation results show that, compared with the DMesh、DTorus and Xmesh, the SD-Torus network can achieve higher performance at the samenetwork costs.
3. The parallel IP address lookup techniques are summarized and classified, and ahierarchical high performance IPv6IP address lookup architecture based on Hash andTree-bitmap is proposed. Furthermore, a parallel IP address lookup architecture based on SD-Torus networks, along with its algorithm are proposed. According to a so-called―Neighborhood Storage‖principle, the full routing information base (RIB) is separatedand mapped onto each SD-Torus node with its six neighbors, therefore to lower thecommunication cost for distributed IP address lookup, decrease the storage footprint andincrease the scalability of the architecture.
4. A massively parallel processing (MPP) IP router SoC architecture base on theSD-Torus network is proposed. The proposed architecture mainly consists of a largenumber of homogenous processing element and a scalable network on chip. The corefunction of an IP router can be accomplished by the distributed processing elementswhich are interconnected by an SD-Torus network, therefore to build a fully distributedpackets forwarding and distributed switching IP router SoC. Experimental results showthat the proposed architecture can achieve high performance and scalability.
5. A general-purpose functional verification platform for IP router SoC is proposedand implemented. As a hardware and software co-verification platform, the fieldprogrammable gate array (FPGA) device is adopted to build the functional verificationhardware platform. Furthermore, by the system configuration through the software, theplatform can be reconfigured to verify different IP router SoCs. With the flexibility ofthe software and the high performance of the FPGA hardware, the functionalverification productivity is improved greatly.
引文
[1] Aweya J. IP router architectures: an overview[J]. International Journal ofCommunication Systems.2001,14(5):447-475.
[2] Császár A, Enyedi G, Retvari G, et al. Converging the evolution of routerarchitectures and IP networks[J]. Network, IEEE.2007,21(4):8-14.
[3] Nguyen K K, Jaumard B. Routing Engine Architecture for Next GenerationRouters: Evolutional Trends[J]. Network Protocols and Algorithms.2009,1(1):62-85.
[4] Aweya J. On the design of IP routers Part1: Router architectures[J]. Journal ofSystems Architecture.2000,46(6):483-512.
[5] Baliga J, Hinton K, Tucker R S. Energy consumption of the Internet[C]//OpticalInternet,2007and the200732nd Australian Conference on Optical Fibre Technology.COIN-ACOFT2007. Joint International Conference on. IEEE,2010.1-3.
[6] Shen X B. Evolution of MPP SoC architecture techniques[J]. Science in ChinaSeries F: Information Sciences.2008,51(6):756-764.
[7] Cisco Systems I. Cisco CRS-1Series Carrier Routing System Getting StartedGuide, Release3.0.[EB/OL]. http://www.cisco.com/en/US/docs/ios_xr_sw/iosxr_r3.0/getting_started/installation/guide/crsget_3.html.
[8] Dally W J, Carvey P, Dennison L. The Avici terabit switch/router[C]//Proc. HotInterconnects.1998.41-50.
[9] Chao H J, Liu B. High performance switches and routers[M]. Hoboken, NewJersey: Wiley-Interscience,2007.
[10] Yang L, Dantu R, Anderson T, et al. Forwarding and control element separation(ForCES) framework[R]. RFC3746.2004.
[11] Hagsand O, Hidell M, Sjodin P. Design and implementation of a distributedrouter[C]//Signal Processing and Information Technology,2005. Proceedings of theFifth IEEE International Symposium on. IEEE,2005.227-232.
[12] Wang W M, Dong L G, Zhuge B. Analysis and implementation of an openprogrammable router based on forwarding and control element separation[J]. Journal ofComputer Science and Technology.2008,23(5):769-779.
[13] Zhang X P, Liu Z H, Zhao Y J, et al. Scalable Router[J]. Chinese Journal ofSoftware.2008,19(6):1452-1464.(In Chinese)张小平，刘振华，赵有健，等.可扩展路由器[J].计算机学报.2008,19(6):1452-1464.
[14] Dai Y, Su J S, Sun Z G. A Parallel Packet Switch Achieving In-Order CellDelivery with Combined-Input-and-Output Queuing Switches[J]. Chinese Journal ofSoftware.2008,19(12):3207-3217.(In Chinese)戴艺，苏金树，孙志刚.一种维序的基于组合输入输出排队的并行交换结构[J].软件学报.2008,19(12):3207-3217.
[15] Dai Y, Su J S, Sun Z G, et al. FIS:A Router Architecture Facilitating High-SpeedIPv6Forwarding[J]. Computer Egineering&Science.2009,31(02):4-6.(In Chinese)戴艺，苏金树，孙志刚，等.一种支持高速IPv6转发的路由器体系结构FIS[J].计算机工程与科学.2009,31(02):4-6.
[16] Dai Y, Sun Z G, Su J S, et al. Reasearch of Key Techniques for Parallel RouterBased on Distributed Fowarding and Switching[J]. Journal of National University ofDefense Technology.2008(03):53-58.(In Chinese)戴艺，孙志刚，苏金树，等.基于分布式转发交换的并行路由器关键技术研究[J].国防科技大学学报.2008(03):53-58.
[17] Sun Z G, Dai Y, Gong Z H. A scalable router architecture for the next generationInternet--MPFS[J]. Science in China(Series E:Information Sciences).2008,38(010):1652-1662.(In Chinese)孙志刚，戴艺，龚正虎.面向下一代互联网的可扩展路由器体系结构——MPFS[J].中国科学: E辑.2008,38(010):1652-1662.
[18] Sun Z G, Dai Y, Gong Z H. MPFS: A truly scalable router architecture for nextgeneration Internet[J]. Science in China Series F: Information Sciences.2008,51(11):1761-1771.
[19] Yue Z H, Zhao Y J, Wu J P. Implementation of Scalable Routers with DirectNetworks[J]. Chinese Journal of Software.2007,18(10):2538-2550.(In Chinese)乐祖晖，赵有健，吴建平.利用直连网络实现可扩展路由器[J].软件学报.2007,18(10):2538-2550.
[20] Yue Z H, Wu J P, Zhao Y J. CR: Scalable Routers Based on a NewArchitecture[J]. Chinese Journal of Software.2007,18(10):2624-2634.(In Chinese)乐祖晖，吴建平，赵有健. CR:基于一类新型结构的可扩展路由器[J].软件学报.2007,18(10):2624-2634.
[21] Nalin T, Takashi I, Morino H, et al. A scalable and high capacity router onmulti-dimension crossbar switch principle[C]//Local Computer Networks,2001.Proceedings. LCN2001.26th Annual IEEE Conference on. IEEE,2001.375-376.
[22] Tzeng N F. Multistage-based switching fabrics for scalable routers[J]. Parallel andDistributed Systems, IEEE Transactions on.2004,15(4):304-318.
[23] He R, Delgado-Frias J G. Fault Tolerant Interleaved Switching Fabrics forScalable High-Performance Routers[J]. Parallel and Distributed Systems, IEEETransactions on.2007,18(12):1727-1739.
[24] Shen X B. Evolution of MPP SoC Architecture[J]. Science in China (SeriesE:Information Sciences).2008,38(006):933-940.(In Chinese)沈绪榜. MPP系统芯片体系结构技术的发展[J].中国科学：E辑.2008,38(006):933-940.
[25] Hu J, Marculescu R. Energy-and performance-aware mapping for regular NoCarchitectures[J]. Computer-Aided Design of Integrated Circuits and Systems, IEEETransactions on.2005,24(4):551-562.
[26] Ogras U Y, Hu J, Marculescu R. Key research problems in NoC design: a holisticperspective[C]//Proceedings of the3rd IEEE/ACM/IFIP international conference onHardware/software codesign and system synthesis. ACM,2005.69-74.
[27] Held J, Bautista J, Koehl S. From a few cores to many: A tera-scale computingresearch overview.[EB/OL]. http://download.intel.com/research/platform/terascale/terascale_overview_paper.pdf.
[28] Team I. Overview of the IBM Blue Gene/P project[J]. IBM Journal of Researchand Development.2008,52(1/2):199-220.
[29] Dally W J. Performance analysis of k-ary n-cube interconnection networks[J].Computers, IEEE Transactions on.1990,39(6):775-785.
[30] Svensson J. Design of a core router using the SoCBUS on-chip network[J].LiTH-ISY-EX.2004,4:3562.
[31] Wiklund D, Ehliar A, Liu D. Design of an Internet core router using the SoCBUSnetwork on chip[C]//Signals, Circuits and Systems,2005. ISSCS2005. InternationalSymposium on. IEEE,2005.513-516.
[32] Taylor M B, Kim J, Miller J, et al. The Raw microprocessor: A computationalfabric for software circuits and general-purpose programs[J]. Micro, IEEE.2002,22(2):25-35.
[33] Agarwal A, Saif U, Anderson J W. The raw router: gigabit routing on ageneral-purpose microprocessor[D]. Massachusetts Institute of Technology,2004.
[34] Chuvpilo G, Wentzlaff D, Amarasinghe S. Gigabit IP routing on raw[C]//Proceedings of the8th International Symposium on High-Performance ComputerArchitecture, Workshop on Network Processors. Citeseer,2002.
[35] Watson G, Mckeown N, Casado M. NetFPGA: A tool for network research andeducation[C]//Workshop on Architecture Research using FPGA Platforms.2006.
[36] Lockwood J W, Mckeown N, Watson G, et al. NetFPGA--an open platform forgigabit-rate network switching and routing[C]//Microelectronic Systems Education,2007. MSE'07. IEEE International Conference on. IEEE,2007.160-161.
[37] Dally W J, Towles B. Route packets, not wires: On-chip interconnectionnetworks[C]//Design Automation Conference,2001. Proceedings. IEEE,2001.684-689.
[38] Hemani A, Jantsch A, Kumar S, et al. Network on chip: An architecture forbillion transistor era[C]//Proceeding of the IEEE NorChip Conference.2000.166-173.
[39] Ye T T. On-chip multiprocessor communication network design and analysis[D].Citeseer,2003.
[40] Marculescu R, Ogras U Y, Peh L S, et al. Outstanding research problems in NoCdesign: system, microarchitecture, and circuit perspectives[J]. Computer-Aided Designof Integrated Circuits and Systems, IEEE Transactions on.2009,28(1):3-21.
[41] Ho R, Mai K W, Horowitz M A. The future of wires[J]. Proceedings of the IEEE.2001,89(4):490-504.
[42] Benini L, De Micheli G. Powering networks on chips: energy-efficient andreliable interconnect design for SoCs[C]//Proceedings of the14th internationalsymposium on Systems synthesis. ACM,2001.33-38.
[43] Kumar S, Jantsch A, Millberg M, et al. A network on chip architecture and designmethodology[C]//VLSI,2002. Proceedings. IEEE Computer Society AnnualSymposium on. Published by the IEEE Computer Society,2002.105-112.
[44] Jantsch A, Tenhunen H. Networks on chip[M]. Springer Netherlands,2003.
[45] Benini L, De Micheli G. Networks on chips: Technology and Tools[M]. MorganKaufmann,2006.
[46] Bjerregaard T, Mahadevan S. A survey of research and practices ofnetwork-on-chip[J]. ACM Computing Surveys (CSUR).2006,38(1):1-51.
[47] Agarwal A, Iskander C, Shankar R. Survey of network on chip (noc) architectures&contributions[J]. Journal of engineering, Computing and Architecture.2009,3(1):21-27.
[48] Ogras U Y, Marculescu R. Energy-and performance-driven NoC communicationarchitecture synthesis using a decomposition approach[C]//Proceedings of theconference on Design, Automation and Test in Europe-Volume1. IEEE ComputerSociety,2005.352-357.
[49] Salminen E, Kulmala A, Hamalainen T D. Survey of Network-on-chipProposals[J]. white paper, OCP-IP.2008:1-13.
[50] Zhou G M. Basic Research on NoC[D]. Hefei: Hefei University of Technology,2005.(In Chinese)周干民. NoC基础研究[D].合肥:合肥工业大学,2005.
[51] Marculescu R, Bogdan P. The chip is the network: Toward a science ofnetwork-on-chip design[M]. Citeseer,2009.
[52] Liu Y Y. Study on Topology Architecture and Communication Paradigm forNetwork-on-Chip[D]. Xi'an: Xidian University,2009.(In Chinese)刘有耀.片上网络拓扑结构与通信方法研究[D].西安:西安电子科技大学,2009.
[53] Duato J, Yalamanchili S, Ni L M. Interconnection networks: An engineeringapproach[M]. Morgan Kaufmann,2003.
[54] Dally W J, Towles B. Principles and practices of interconnection networks[M].Morgan Kaufmann,2004.
[55] Knuth D E. The art of computer programming. Vol.3, Sorting and Searching[M].Reading, MA: Addison-Wesley,1973.
[56] Waldvogel M, Varghese G, Turner J, et al. Scalable high speed IP routinglookups[C]//Proceedings of the ACM SIGCOMM'97conference on Applications,technologies, architectures, and protocols for computer communication. Cannes, France:ACM,1997.25-36.
[57] Lampson B, Srinivasan V, Varghese G. IP lookups using multiway andmulticolumn search[J]. IEEE/ACM Transactions on Networking (TON).1999,7(3):324-334.
[58] Jain R. A Comparison of Hashing Schemes for Address Lookup in ComputerNetworks[J]. IEEE TRANSACTIONS ON COMMUNICATIONS.1992,40(10):1570-1573.
[59] Yu D, Smith B C, Wei B. Forwarding engine for fast routing lookups andupdates[C]//Global Telecommunications Conference,1999. GLOBECOM'99.1999.1556-1564.
[60] Ravikumar V C, Mahapatra R N. TCAM architecture for IP lookup using prefixproperties[J]. IEEE MICRO.2004:60-68.
[61] Zheng K, Hu C, Lu H, et al. An ultra high throughput and power efficientTCAM-based IP lookup engine[C]//IEEE INFOCOM. Citeseer,2004.1984-1994.
[62] Ruiz-Sánchez M, Biersack E W, Dabbous W. Survey and taxonomy of IP addresslookup algorithms[J]. IEEE network.2001,15(2):8-23.
[63] Postel J. Internet protocol[R]. RFC791,1981.
[64] Mogul J, Postel J. Internet standard subnetting procedure[R]. RFC950,1985.
[65] Fuller V, Li T, Yu J, et al. Classless Inter-Domain Routing (CIDR): an addressassignment and aggregation strategy[R]. RFC1519,1993.
[66] Rekhter Y, Li T. An architecture for IP address allocation with CIDR[R]. RFC1518,1993.
[67] Morrison D R. PATRICIA-practical algorithm to retrieve information coded inalphanumeric[J]. Journal of the ACM (JACM).1968,15(4):514-534.
[68] Sklower K. A tree-based routing table for Berkeley Unix[C]//Proceedings of theWinter1991USENIX Conference.1991.93-103.
[69] Srinivasan V, Varghese G. Faster IP lookups using controlled prefix expansion[J].ACM SIGMETRICS Performance Evaluation Review.1998,26(1):1-10.
[70] Gupta P, Lin S, Mckeown N. Routing lookups in hardware at memory accessspeeds[C]//IEEE INFOCOM. Citeseer,1998.1241-1247.
[71] Nilsson S, Karlsson G. IP-address lookup using LC-tries[J]. IEEE Journal onselected Areas in Communications.1999,17(6):1083-1092.
[72] Eatherton W, Varghese G, Dittia Z. Tree bitmap: hardware/software IP lookupswith incremental updates[J]. ACM SIGCOMM Computer Communication Review.2004,34(2):97-122.
[73] Taylor D E, Turner J S, Lockwood J W, et al. Scalable IP lookup for Internetrouters[J]. IEEE journal on selected areas in communications.2003,21(4):522-534.
[74] Dharmapurikar S, Krishnamurthy P, Taylor D E. Longest prefix matching usingbloom filters[C]//Proceedings of the2003conference on Applications, technologies,architectures, and protocols for computer communications. ACM New York, NY, USA,2003.201-212.
[75] Li Y K, Pao D. Address lookup algorithms for IPv6[J]. IEEProceedings-Communications.2006,153(6):909-918.
[76] Chu Y S, Su H K, Lin P F, et al. IC Design of IPv6Routing Lookup for HighSpeed Networks[J]. Computational Science–ICCS2006.2006:184-187.
[77] Zheng K, Liu Z, Liu B. A scalable IPv6route lookup scheme via dynamicvariable-stride bitmap compression and path compression[J]. Computercommunications.2006,29(16):3037-3050.
[78] Chen C H, Hsu C H, Wang C C. Scalable IPv6Lookup/Update Design forHigh-Throughput Routers[J]. Journal of Internet Technology.2007,8(3):261-270.
[79] Li Z, Zheng D, Ma Y. Tree, Segment Table, and Route Bucket: A Multi-StageAlgorithm for IPv6Routing Table Lookup[C]//INFOCOM2007.26th IEEEInternational Conference on Computer Communications. IEEE. IEEE,2007.2426-2430.
[80] Sun Q, Zhao X, Huang X, et al. A Scalable Exact matching in Balance TreeScheme for IPv6Lookup[C]//ACM SIGCOMM.2007.27-31.
[81] Sun Q, Huang X H, Zhou X J, et al. A dynamic binary hash scheme for IPv6lookup[C]//Global Telecommunications Conference,2008. IEEE GLOBECOM2008.IEEE. IEEE,2008.1-5.
[82] Li Z, Deng X, Ma H, et al. Divide-and-conquer: a scheme for IPv6addresslongest prefix matching[C]//High Performance Switching and Routing,2006Workshopon. IEEE,2006.6.
[83] Jiang W, Prasanna V K. Sequence-preserving parallel IP lookup using multipleSRAM-based pipelines[J]. Journal of Parallel and Distributed Computing.2009,69(9):778-789.
[84] Song H, Hao F, Kodialam M, et al. Ipv6lookups using distributed and loadbalanced bloom filters for100G/s core router line cards[C]//INFOCOM2009, IEEE.IEEE,2009.2518-2526.
[85] Han J G, Du H M. Formal Verification of the Digital Hardware[M]. Beijing:Beijing university press,2001.(In Chinese)韩俊刚，杜慧敏.数字硬件的形式化验证[M].北京:北京大学出版社,2001.
[86] Brahme D, Cox S, Gallo J, et al. The transaction-based verification methodology[J]. Cadence Design Systems, Inc.2000.
[87] Foster H, Krolnik A, Lacey D. Assertion-based design[M]. Springer,2004.
[88] Adiga N R, Blumrich M A, Chen D, et al. Blue Gene/L torus interconnectionnetwork[J]. IBM Journal of Research and Development.2005,49(2.3):265-276.
[89] Tse E S H. Switch fabric design for high performance IP routers: A survey[J].Journal of Systems Architecture.2005,51(10-11):571-601.
[90] Gu H, Liu Z, Wang K. Distributed adaptive routing algorithms in Torusnetworks[J]. Journal of Xidian University.2006,33(3):352-358.(In Chinese)顾华玺，刘增基，王琨，等. Torus网络中分布式自适应路由算法[J].西安电子科技大学学报(自然科学版).2006,33(3):352-358.
[91] Wang Y G, Du H M, Shen X B. Virtual Channel Load-Balanced RoutingAlgorithm for Torus Networks[J]. The Journal of China Universities of Posts andTelecommunications.2011,18(1):70-76.
[92] Glass C J, Ni L M. The turn model for adaptive routing[C]//Proceedings of the19th annual international symposium on Computer architecture. ACM,1992.278-287.
[93] Jain L. Nirgam.[EB/OL]. http://www.nirgam.ecs.soton.ac.uk.
[94] Wang Y G, Du H M, Shen X B. Topological properties and routing algorithm forsemi-diagonal torus networks[J]. The Journal of China Universities of Posts andTelecommunications.2011,18(5):64-70.
[95] Ming O Y, Zhu B, Liang H G, et al. Networks on Chip Based on DiagonalInterlinked Mesh Topology Structure[J]. Computer Engineering.2009,35(022):100-102.(In Chinese)欧阳一鸣，朱兵，梁华国，等.基于对角互连网格拓扑结构的片上网络[J].计算机工程.2009,35(022):100-102.
[96] Zhu X J, Hu W W, Ma K, et al. Xmesh: A Mesh-Like Topology for Network onChip[J]. Chinese Journal of Software.2007,18(9):2194-2204.(In Chinese)朱晓静，胡伟武，马可，等. Xmesh:一个mesh-like片上网络拓扑结构[J].计算机学报.2007,18(9):2194-2204.
[97] Huston G. AS65000-BGP Table Statistics.[EB/OL]. http://bgp.potaroo.net/as2.0/bgp-active.html.
[98] Huston G. The BGP Instability Report.[EB/OL]. http://bgpupdates.potaroo.net/instability/bgpupd.html.
[99] Hinden R, Deering S. Internet protocol version6(IPv6) addressing architecture
[R]. RFC3513,2003.
[100] Brackett C A, Res B C, Morristown N J. Dense wavelength division multiplexingnetworks: principles and applications[J]. IEEE Journal on Selected Areas inCommunications.1990,8(6):948-964.
[101] Patterson D A. Latency lags bandwith[J]. Communications of the ACM.2004,47(10):71-75.
[102] Patterson D A, Hennessy J L, Ashenden P J. Computer organization and design:the hardware/software interface[M]. Morgan Kaufmann,2004.
[103] Hennessy J L, Patterson D A, Goldberg D, et al. Computer architecture: aquantitative approach[M]. Morgan Kaufmann,2003.
[104] Chiueh T, Pradhan P. High-performance IP routing table lookup using CPUcaching[C]//IEEE INFOCOM'99. Eighteenth Annual Joint Conference of the IEEEComputer and Communications Societies. Proceedings. New York, NY: IEEE,1999.1421-1428.
[105] Talbot B, Sherwood T, Lin B. IP caching for terabit speed routers[J].GLOBECOM-NEW YORK-.1999,2:1565-1569.
[106] Venkatesh K, Aravind S, Ganapath Ram R, et al. A high performance parallel IPlookup technique using distributed memory organization[C]//International Conferenceon Information Technology: Coding and Computing (ITCC'04). Las Vegas, Nevada:IEEE Computer Society,2004.792-797.
[107] Lim H, Seo J H, Jung Y J. High speed IP address lookup architecture usinghashing[J]. IEEE Communications Letters.2003,7(10):502-504.
[108] Rojas-Cessa R, Ramesh L, Dong Z, et al. Parallel Search Trie-Based Scheme forFast IP Lookup[C]//IEEE Global Telecommunications Conference,2007.GLOBECOM'07.2007.210-214.
[109] Zheng K. Research on High Performance IP Route Lookup and PacketClassification[D]. Beijing: Tsinghua University,2006.(In Chinese)郑凯.高性能IP路由查找和分组分类技术的研究[D].北京:清华大学,2006.
[110] Baboescu F, Tullsen D M, Rosu G, et al. A tree based router search enginearchitecture with single port memories[C]//Proceedings of the32nd annualinternational symposium on Computer Architecture. IEEE Computer Society,2005.123-133.
[111] Kumar S, Becchi M, Crowley P, et al. CAMP: fast and efficient IP lookuparchitecture[C]//Proceedings of the2006ACM/IEEE symposium on Architecture fornetworking and communications systems. San Jose, California, USA: ACM,2006.51-60.
[112] Jiang W, Prasanna V K. A memory-balanced linear pipeline architecture fortrie-based IP lookup[C]//15th Annual IEEE Symposium on High-PerformanceInterconnects (HOTI2007). Stanford, CA:2007.83-90.
[113] Jiang W, Prasanna V K. Parallel IP lookup using multiple SRAM-basedpipelines[C]//Parallel and Distributed Processing,2008. IPDPS2008. IEEEInternational Symposium on. Citeseer,2008.14-18.
[114] Jiang W, Wang Q, Prasanna V K. Beyond TCAMs: An SRAM-based parallelmulti-pipeline architecture for terabit IP lookup[C]//INFOCOM2008. The27thConference on Computer Communications. IEEE. Phoenix, AZ: Citeseer,2008.1786-1794.
[115] Hasan J, Vijaykumar T N. Dynamic pipelining: making IP-lookup trulyscalable[C]//Proceedings of the2005conference on Applications, technologies,architectures, and protocols for computer communications. Philadelphia, Pennsylvania,USA: ACM,2005.205-216.
[116] Chang Y K, Liu Y C, Kuo F C. A Pipelined IP Forwarding Engine with FastUpdate[C]//Proceedings of the2009International Conference on AdvancedInformation Networking and Applications. Bradford, United Kingdom: IEEE ComputerSociety,2009.263-269.
[117] Hung L C, Chen Y C. Parallel Table Lookup for Next Generation Internet[C]//Proceedings of the200832nd Annual IEEE International Computer Software andApplications Conference. IEEE Computer Society,2008.52-59.
[118] Kumar V, Grama A, Gupta A, et al. Introduction to parallel computing[M].Benjamin/Cummings USA,1994.
[119] Dally W J. Scalable switching fabrics for Internet routers.[EB/OL].http://www.coreinc.com/technology/whitepapers/TSRfabric-WhitePaper.pdf.
[120] Ni L M, Mckinley P K. A survey of wormhole routing techniques in directnetworks[J]. IEEE computer.1993,26(2):62-76.
[121] Gaughan P T, Yalamanchili S. Adaptive routing protocols for hypercubeinterconnection networks[J]. IEEE Computer.1993,26(5):12-23.
[122] Wang Y G, Du H M, Yang K P. Two-stage IPv6Address Lookup Scheme Basedon Hash Tables and Tree Bitmaps[J]. Computer Science.2010,37(9):36-39,80.(InChinese)王亚刚，杜慧敏，杨康平.使用Hash表和树位图的两级IPv6地址查找算法[J].计算机科学.2010,37(9):36-39,80.
[123] Wang Y G, Du H M, Yang K P. On Memory Management of Tree-bitmapAlgorithm for IP Address Lookup[C]//The2nd International Symposium ComputerScience and Computational Technology (ISCSCT2009).2009.418-422.
[124] Conta A, Deering S. RFC2473: Generic packet tunneling in IPv6specification[S].1998.
[125] Wang Y G, Du H M, Wang M M, et al. Scalable Parallel IP Address LookupArchitecture based on2D-Torus network[C]//Information Science and Engineering(ICISE),20102nd International Conference on. IEEE,2010.1483-1486.
[126] Chen M S, Shin K G, Kandlur D D. Addressing, routing, and broadcasting inhexagonal mesh multiprocessors[J]. Computers, IEEE Transactions on.1990,39(1):10-18.
[127] Zhao Y, Yue Z, Wu J, et al. Topological properties and routing algorithms incellular router[C]//Networking and Services,2006. ICNS'06. International conferenceon. IEEE,2006.101.
[128] Jain L. Nirgam[J]. University of Southampton UK, http://www. nirgam. ecs. soton.ac. uk.
[129] Zhu X D, Li L M. Analysis of Switching Fabrics Employing DirectInterconnection Networks[J]. Journal of University of Electronic Science andTechnology of China.2003,32(3):272-275.(In Chinese)朱旭东，李乐民.直接互连结构在数据交换中的应用分析[J].电子科技大学学报.2003,32(3):272-275.
[130] Scheme of constructing scalable packet switching fabrics with Torus networks[J].Application Research of Computers.2008,25(3):866-868.(In Chinese)王宏，许都，李乐民.用Torus网络构建可扩展分组交换结构的设计方案[J].计算机应用研究.2008,25(3):866-868.
[131] Rashinkar P, Paterson P, Singh L. System-on-a-chip Verification: Methodologyand Techniques[M]. Springer,2000.
[132] Spear C. SystemVerilog for verification: a guide to learning the testbenchlanguage features[M]. Springer Verlag,2008.