并行路由器体系结构及其关键技术研究
|
摘要
Internet网络流量、规模和应用的快速发展对互联网核心路由器设计提出了重大挑战。随着光纤传输带宽和入网主机数目的日益增长,路由器交换容量及端口密度难以适应网络流量的增长需求;随着网络规模的急剧扩张尤其是多宿主技术的广泛应用,路由器转发能力难以适应FIB(Forwarding Information Base)表容量的指数级增长;随着IPv6、QoS、组播、安全等应用的发展,路由器报文处理能力难以解决网络流量增长和报文处理复杂度增长之间的矛盾。在路由器中引入并行处理技术的并行路由器体系结构为提高路由器转发交换能力提供了有效途径。
采用并行设计给路由器带来了负载均衡和报文乱序两大问题。负载均衡是实现延迟和吞吐率保证的关键,但负载均衡可能导致报文乱序,进而可能触发TCP连接不必要的重传和超时,降低TCP吞吐率,增加报文延迟。如何解决这对矛盾是并行路由器设计的难点。已有的维序调度算法,要么需要复杂的通信或集中式的调度,要么依赖简单的分布式调度而缺乏吞吐率保证。针对以上问题,本文通过深入分析并行路由器体系结构队列模型和信元分布特性,提出了兼顾负载均衡和报文保序,降低调度复杂性和通信开销,并能提供延迟和吞吐率保证的分布式负载分配方法和协同调度机制。
现有的路由器包含转发和交换两个连续的处理阶段,它们在硬件实现上是分离的,报文转发与交换的串行执行不利于路由器并行性的开发。本文原创性地提出一种同时开发转发与交换平行度的报文处理机制,将FIB查找功能分解并映射到交换网络中分布执行,为解决目前骨干路由器设计所面临的FIB处理极限问题提供理论、技术和实践支持。
论文针对目前并行路由器设计所面临的负载均衡、报文乱序、延迟和吞吐率保证、通信复杂性及FIB极限等问题进行了深入研究,主要研究成果及创新包括以下几个方面:
1.针对并行路由器设计负载均衡与报文保序之间的矛盾,提出一种基于流映射的细粒度负载分配算法UFFS-k(Uniform Fne-grain Frame Spreading,k为聚合粒度,简称UFFS-k),UFFS-k算法分布于各输入端口独立执行,根据本地VOQ队列信息分派信元,不需要任何通信开销,以O(1)时间复杂度实现了100%的吞吐率并能保证报文的顺序。模拟结果显示,UFFS-k算法能够有效降低信元延迟并具有较好的负载均衡特性。
2.针对异构型并行路由器设计受限于通信及调度的复杂性,难以保证报文的顺序且硬件实现复杂的问题。基于CIOQ交换平面,提出一种具有按序排队特性的IOQ(In-order Queueing)PPS体系结构,在输入端轮询(round robin)分派算法和中间级CIOQ交换平面同步调度算法之间设计了一种简单的协同调度机制,保证同一条流的信元按序从交换平面读出,避免了输出端报文重定序开销。IOQPPS在多个独立的交换平面间执行报文流级的负载均衡,消除了中间级交换平面的加速需求。模拟结果表明,IOQ PPS在同类PPS设计中具有最优延迟性能。
3.针对并行路由器设计所面临的FIB处理极限问题,提出一种在交换网络中执行转发操作的新型报文:处理机制FIS(Forwarding in Switching)。FIS将IP查找功能进行分解并映射到多个硬件同构的具有独立转发交换功能的FSN(Forwardingand Switching Node)结点分布执行,通过分解FIB表,构建FIB表到FSN结点的映射,降低了IP查找复杂度;FIB表的分布式存储,解决了并行查找机制访存瓶颈问题,提高了路由器FIB扩容能力。论文对FIS实现关键技术——转发表的分解、子树到FSN结点的映射及面向FIS的IP查找机制进行了深入的研究,给出了相应的解决方案,为FIS原型验证系统的设计与实现奠定了基础。
4.面向FIS处理特性,提出了基于前缀范围的IPv6二分查找算法PSB-BS(Prefix Scope Based Binary Search):基于前缀范围的子树表示法消除了对路径信息的保存,降低了存储开销;基于前缀范围的二分查找策略能有效压缩查找路径,减少访存次数。通过构造PSB-BS算法二分查找树实现IPv6转发表到FSN结点的映射,仿真实验结果表明,随前缀数目的增加,每一级FSN结点的平均查找次数几乎没什么变化,反映了PSB-BS算法良好的可扩展性。
综上所述,本文针对并行路由器设计的几个关键问题提出了有效的解决方案,对提高路由器的性能、规模、可扩展性,以及推进路由器并行技术的实用化具有一定的理论意义和应用价值。
Continuing growth in traffic, the size of Internet as well as the Internet applications puts forward great challenge to backbone router design. First, the capacity and port density of the switch can hardly keep up with the growth of traffic resulting from increasing link speeds and the number of hosts on the Internet. Second, IP-lookup performance in core routers can hardly keep up with the growth of FIB size resulting from widely used multi-homed technology and increased Internet size. Third, with the development of Internet applications such as IPv6, QoS, multicast, security, etc. packet process power can hardly fix the contradiction between increasing packet rate and increasing complexity of packet processing. Recently, parallel router architectures introducing parallelism inside routers appears to be an efficient way to scale Internet routers to very high capacities and forwarding rates.
Parallel design brings load balancing and packet reordering problems inside routers. Load balancing is prerequisite to achieving delay and throughput guarantees in parallel router architectures. Unfortunately, load balancing may incur out-of-order packets which trigger unnecessary retransmissions and TCP timeouts, thus decreasing TCP throughout and increasing packet delay. How to deal with this contradiction is a crucial problem in parallel router design. The existing scheduling mechanisms maintaining packet ordering either require complex, centralized schedulers, or rely on simple distributed scheduling algorithms that lack throughput guarantees. Aiming at the problems above, by thorough analyzing queuing model and distribution properties of cells in parallel router architectures we propose a load-balancing technique and a cooperative scheduling mechanism which are all distributed and can enforce packet ordering and load-balancing, reduce complexity of scheduling and communication overhead as well as provide delay and throughput guarantees.
A router logically consists of two consecutive stages namely forwarding stage and switching stage. These two processing stages are implemented in different hardware components and performed in order, which hinders parallelism development inside routers. We originally propose a distinct packet processing mechanism concurrently exploiting parallelism of switching and forwarding operations. This packet processing mechanism partitions FIB lookup function and distributes FIB lookups to switch fabrics so as to distributedly perform packet forwarding in the process of packet switching, which provide theoretical, technical and practical value for solving FIB limits confronting modern routers.
We make comprehensive research on crucial problems of load balancing, packet reordering, delay and throughput guarantees, communication complexity and FIB limits for parallel router design. The major contributions of this dissertation are as follows.
1. To make a better tradeoff between load balancing and packet ordering we propose a fine-grained frame dispatching algorithm called UFFS-k (Uniform Fine-grain Frame Spreading (UFFS-k, where k is the aggregate factor) based on flow mapping which is distributed and can operate independently in each input. UFFS-k dispatches cells based on local VOQs' state information, moreover, without any communication overhead it guarantees packet ordering and achieves 100% throughput with 0(1) time complexity. As the simulation results demonstrate, UFFS-k reduces packet delay considerably and has better capacity of load balancing.
2. Due to communication and scheduling complexity, heterogeneous parallel router architectures have difficulties in maintaining packet ordering and implementing with low-cost hardware components. We propose an IOQ (In-order Queuing) PPS architecture based on CIOQ switch planes. By using a simple collaborative scheduling mechanism between round-robin demultiplexing at inputs and synchronous switching at central switch planes, our scheme guarantees a way for cells of a flow to be read in order from different switch planes, thus avoiding packet reordering at output ports. IOQ PPS achieves packet-level load balancing over multiple independent switch planes and eliminates the speedup requirement for the internal switch planes. As the experiment results demonstrate, IOQ PPS offers improved delay performance compared to existing PPS designs.
3. To address FIB limits confronting parallel router design, we propose a parallel packet process mechanism performing packet forwarding in switch fabrics—FIS (forwarding in switching) which partitions IP lookup function and distributes IP lookups to multiple lower speed and heterogeneous nodes called FSN (Forwarding and Switching Node) which performs forwarding and switching independently. By partitioning FIB table and by constructing mapping relationship between FIB table and FSNs, IP-lookup complexity is reduced considerably. Further, the distributed storing of FIB table among FSNs eliminates memory bottleneck of parallel lookup mechanism, thus improving the FIB scalability of modern routers. We make comprehensive research on the key technologies of FIS mechanism including the partition of routing table, the logical mapping from subtries to FSNs, as well as the FIS-oriented IP-lookup mechanism. Our work underlies the design and implementation of FIS hardware prototype system.
4. We propose an IPv6 binary lookup algorithm based on prefix scope called PSB-BS (prefix scope based binary search) for putting FIS in practice. The efficiency of PSB-BS algorithm can be attributed to two key aspects. First, the subtrie format based on prefix scope eliminates the presentation of path information which contributes to a reduction in the memory space occupied by the search structure. Second, the binary search scheme based on prefix scope compresses the search path, thus reducing the number of memory access. We map IPv6 forwarding table to FSNs in FIS by constructing binary search trie of PSB-BS algorithm. The experiment results demonstrate the average search time of FSN varies stably with the increased number of prefixes, which reflect better scalability of PSB-BS algorithm.
In summary, our work presents solutions to several key problems of parallel router design, and has academic and practical value for improving the performance, size and scalability of modern routers and advancing the practicability of parallel technologies for routers.
采用并行设计给路由器带来了负载均衡和报文乱序两大问题。负载均衡是实现延迟和吞吐率保证的关键,但负载均衡可能导致报文乱序,进而可能触发TCP连接不必要的重传和超时,降低TCP吞吐率,增加报文延迟。如何解决这对矛盾是并行路由器设计的难点。已有的维序调度算法,要么需要复杂的通信或集中式的调度,要么依赖简单的分布式调度而缺乏吞吐率保证。针对以上问题,本文通过深入分析并行路由器体系结构队列模型和信元分布特性,提出了兼顾负载均衡和报文保序,降低调度复杂性和通信开销,并能提供延迟和吞吐率保证的分布式负载分配方法和协同调度机制。
现有的路由器包含转发和交换两个连续的处理阶段,它们在硬件实现上是分离的,报文转发与交换的串行执行不利于路由器并行性的开发。本文原创性地提出一种同时开发转发与交换平行度的报文处理机制,将FIB查找功能分解并映射到交换网络中分布执行,为解决目前骨干路由器设计所面临的FIB处理极限问题提供理论、技术和实践支持。
论文针对目前并行路由器设计所面临的负载均衡、报文乱序、延迟和吞吐率保证、通信复杂性及FIB极限等问题进行了深入研究,主要研究成果及创新包括以下几个方面:
1.针对并行路由器设计负载均衡与报文保序之间的矛盾,提出一种基于流映射的细粒度负载分配算法UFFS-k(Uniform Fne-grain Frame Spreading,k为聚合粒度,简称UFFS-k),UFFS-k算法分布于各输入端口独立执行,根据本地VOQ队列信息分派信元,不需要任何通信开销,以O(1)时间复杂度实现了100%的吞吐率并能保证报文的顺序。模拟结果显示,UFFS-k算法能够有效降低信元延迟并具有较好的负载均衡特性。
2.针对异构型并行路由器设计受限于通信及调度的复杂性,难以保证报文的顺序且硬件实现复杂的问题。基于CIOQ交换平面,提出一种具有按序排队特性的IOQ(In-order Queueing)PPS体系结构,在输入端轮询(round robin)分派算法和中间级CIOQ交换平面同步调度算法之间设计了一种简单的协同调度机制,保证同一条流的信元按序从交换平面读出,避免了输出端报文重定序开销。IOQPPS在多个独立的交换平面间执行报文流级的负载均衡,消除了中间级交换平面的加速需求。模拟结果表明,IOQ PPS在同类PPS设计中具有最优延迟性能。
3.针对并行路由器设计所面临的FIB处理极限问题,提出一种在交换网络中执行转发操作的新型报文:处理机制FIS(Forwarding in Switching)。FIS将IP查找功能进行分解并映射到多个硬件同构的具有独立转发交换功能的FSN(Forwardingand Switching Node)结点分布执行,通过分解FIB表,构建FIB表到FSN结点的映射,降低了IP查找复杂度;FIB表的分布式存储,解决了并行查找机制访存瓶颈问题,提高了路由器FIB扩容能力。论文对FIS实现关键技术——转发表的分解、子树到FSN结点的映射及面向FIS的IP查找机制进行了深入的研究,给出了相应的解决方案,为FIS原型验证系统的设计与实现奠定了基础。
4.面向FIS处理特性,提出了基于前缀范围的IPv6二分查找算法PSB-BS(Prefix Scope Based Binary Search):基于前缀范围的子树表示法消除了对路径信息的保存,降低了存储开销;基于前缀范围的二分查找策略能有效压缩查找路径,减少访存次数。通过构造PSB-BS算法二分查找树实现IPv6转发表到FSN结点的映射,仿真实验结果表明,随前缀数目的增加,每一级FSN结点的平均查找次数几乎没什么变化,反映了PSB-BS算法良好的可扩展性。
综上所述,本文针对并行路由器设计的几个关键问题提出了有效的解决方案,对提高路由器的性能、规模、可扩展性,以及推进路由器并行技术的实用化具有一定的理论意义和应用价值。
Continuing growth in traffic, the size of Internet as well as the Internet applications puts forward great challenge to backbone router design. First, the capacity and port density of the switch can hardly keep up with the growth of traffic resulting from increasing link speeds and the number of hosts on the Internet. Second, IP-lookup performance in core routers can hardly keep up with the growth of FIB size resulting from widely used multi-homed technology and increased Internet size. Third, with the development of Internet applications such as IPv6, QoS, multicast, security, etc. packet process power can hardly fix the contradiction between increasing packet rate and increasing complexity of packet processing. Recently, parallel router architectures introducing parallelism inside routers appears to be an efficient way to scale Internet routers to very high capacities and forwarding rates.
Parallel design brings load balancing and packet reordering problems inside routers. Load balancing is prerequisite to achieving delay and throughput guarantees in parallel router architectures. Unfortunately, load balancing may incur out-of-order packets which trigger unnecessary retransmissions and TCP timeouts, thus decreasing TCP throughout and increasing packet delay. How to deal with this contradiction is a crucial problem in parallel router design. The existing scheduling mechanisms maintaining packet ordering either require complex, centralized schedulers, or rely on simple distributed scheduling algorithms that lack throughput guarantees. Aiming at the problems above, by thorough analyzing queuing model and distribution properties of cells in parallel router architectures we propose a load-balancing technique and a cooperative scheduling mechanism which are all distributed and can enforce packet ordering and load-balancing, reduce complexity of scheduling and communication overhead as well as provide delay and throughput guarantees.
A router logically consists of two consecutive stages namely forwarding stage and switching stage. These two processing stages are implemented in different hardware components and performed in order, which hinders parallelism development inside routers. We originally propose a distinct packet processing mechanism concurrently exploiting parallelism of switching and forwarding operations. This packet processing mechanism partitions FIB lookup function and distributes FIB lookups to switch fabrics so as to distributedly perform packet forwarding in the process of packet switching, which provide theoretical, technical and practical value for solving FIB limits confronting modern routers.
We make comprehensive research on crucial problems of load balancing, packet reordering, delay and throughput guarantees, communication complexity and FIB limits for parallel router design. The major contributions of this dissertation are as follows.
1. To make a better tradeoff between load balancing and packet ordering we propose a fine-grained frame dispatching algorithm called UFFS-k (Uniform Fine-grain Frame Spreading (UFFS-k, where k is the aggregate factor) based on flow mapping which is distributed and can operate independently in each input. UFFS-k dispatches cells based on local VOQs' state information, moreover, without any communication overhead it guarantees packet ordering and achieves 100% throughput with 0(1) time complexity. As the simulation results demonstrate, UFFS-k reduces packet delay considerably and has better capacity of load balancing.
2. Due to communication and scheduling complexity, heterogeneous parallel router architectures have difficulties in maintaining packet ordering and implementing with low-cost hardware components. We propose an IOQ (In-order Queuing) PPS architecture based on CIOQ switch planes. By using a simple collaborative scheduling mechanism between round-robin demultiplexing at inputs and synchronous switching at central switch planes, our scheme guarantees a way for cells of a flow to be read in order from different switch planes, thus avoiding packet reordering at output ports. IOQ PPS achieves packet-level load balancing over multiple independent switch planes and eliminates the speedup requirement for the internal switch planes. As the experiment results demonstrate, IOQ PPS offers improved delay performance compared to existing PPS designs.
3. To address FIB limits confronting parallel router design, we propose a parallel packet process mechanism performing packet forwarding in switch fabrics—FIS (forwarding in switching) which partitions IP lookup function and distributes IP lookups to multiple lower speed and heterogeneous nodes called FSN (Forwarding and Switching Node) which performs forwarding and switching independently. By partitioning FIB table and by constructing mapping relationship between FIB table and FSNs, IP-lookup complexity is reduced considerably. Further, the distributed storing of FIB table among FSNs eliminates memory bottleneck of parallel lookup mechanism, thus improving the FIB scalability of modern routers. We make comprehensive research on the key technologies of FIS mechanism including the partition of routing table, the logical mapping from subtries to FSNs, as well as the FIS-oriented IP-lookup mechanism. Our work underlies the design and implementation of FIS hardware prototype system.
4. We propose an IPv6 binary lookup algorithm based on prefix scope called PSB-BS (prefix scope based binary search) for putting FIS in practice. The efficiency of PSB-BS algorithm can be attributed to two key aspects. First, the subtrie format based on prefix scope eliminates the presentation of path information which contributes to a reduction in the memory space occupied by the search structure. Second, the binary search scheme based on prefix scope compresses the search path, thus reducing the number of memory access. We map IPv6 forwarding table to FSNs in FIS by constructing binary search trie of PSB-BS algorithm. The experiment results demonstrate the average search time of FSN varies stably with the increased number of prefixes, which reflect better scalability of PSB-BS algorithm.
In summary, our work presents solutions to several key problems of parallel router design, and has academic and practical value for improving the performance, size and scalability of modern routers and advancing the practicability of parallel technologies for routers.
引文
[1]Prabhakar B.EE384x:Packet Switch Architectures.Winter 2006,Available at http://tiny-tera.stanford.edu/～nickm/talks/index.html
[2]管剑波,苏金树,卢锡城.支持单一POP应用的异构路由器聚合交换技术.国防科学技术大学学报,2005,27(5):13-17
[3]McKeown N.Growth in router capacity.IPAM Workshop,Oct.2003,Lake Arrowhead,CA.Available at http://tiny-tera.stanford.edu/～nickm/talks/index.html
[4]Odlyzko A.M.Comments on the Larry Roberts and Caspian networks study of Internet traffic growth.The Cook Report on the Internet,Dec.2001:12-15
[5]Odlyzko A.M.The current state and likely evolution of the Internet.Proc.of Globecom'99,1999:1869-1875
[6]McKeown N.Internet Routers Past,Present and Future.British Computer Society,June.2006,CA.Available at http://tiny-tera.stanford.edu/～nickm/talks/index.html
[7]Bradner S,McQuaid J.Benchmarking methodology for network interconnect devices.RFC 2544,1999.http://www.ietf.org/rfc/rfc2544.txt
[8]Bradner S,McQuaid J.Benchmarking methodology for network interconnect devices.RFC 2544,1999.http://www.ietf.org/rfc/rfc2544.txt
[9]McKeown N.Scheduling algorithms for input-queued switches[PhD Thesis].University of California,Berkeley,1995.
[10]McKeown N.The iSLIP scheduling algorithm for input-queued switches[J].IEEE/ACM Trans.Networking,Apr.1999,vol.7(2).
[11]Anderson T E,Owicki S S,Saxe J B,Thacker C P.High-speed switch scheduling for local-area networks[J].ACM Transactions on Computer Systems,1999,vol.11(4):319-352.
[12]Marsan M,Bianco A,Leonardi E,Milla L.RPA:A flexible scheduling algorithm for input buffered switches[J].IEEE Transactions on Communications,1999,vol.47(12):1921-1933.
[13]Mekkittikui A,McKeown N.A practical scheduling algorithm to achieve 100%throughput in input-queued switches[C].In:Akyildiz I,ed.Proceedings of the IEEE INFOCOM.San FranCisco,IEEE Communications Society,1998.792-799
[14]Duan H,Lockwood J,Kang S,Will J.A high performance OC12/OC48 queue design prototype for input buffered atm switches[C].In:Hasegawa T,ed.Proceedings of the IEEE INFOCOM.Kobe,IEEE Communications Society,1997.20-28
[15]Iyer S,Kompella R,McKeown N.Analysis of a memory architecture for fast packet buffers[C].In:Proceedings of the IEEE Workshop on High Performance Switching and Routing, 2001. 368-373
[16] Shi L, Liu B, Li W, Wu B, Liu Y. DS-PPS: A practical framework to guarantee differentiated QoS in terabit routers with parallel packet switch [C]. In: 25th IEEE INFOCOM. Barcelona, 2006
[17] Patterson D. and Hennessy J. Computer architecture, a quantitative approach.Morgan Kaufmann, 1996.
[18] Rambus, inc., los altos, ca. [online]. Available: Http://www.Rambus.Com
[19]Rekhter Y, Li T. An architecture for IP address allocation with CIDR. RFC 1518,Sep. 1993. Available at http://www.ietf.org/rfc/rfc1518.txt
[20] Fuller V, Li T, Yu J, Varadhan K. Classless inter-domain routing (CIDR): an address assignment and aggregation strategy. RFC 1519, Sep. 1993. Available at http://www.ietf.org/rfc/rfc1519.txt
[21] Ruiz-Sanchez M, Biersack E, and Dabbous W. Survey and taxonomy of IP address lookup algorithms. IEEE Network, March 2001
[22]Tzeng H, Przygienda T. On fast address-lookup algorithms. IEEE Journal on Selected Areas in Communications, 1999, 17(6):1067-1082.
[23] Aslam A, Christensen K J. A parallel packet switch with multiplexors containing virtual input queues [J]. Computer Communications 2004, vol. 27: 1248-1263.
[24]Mneimneh S, K. Siu. Scheduling unsplittable flows using parallel switches [C]. In:Proceedings of IEEE ICC 2002.2410-2415
[25] Khotimsky D, Krishnan S. Towards the recognition of parallel packet switches [C].In: Proceedings of the Gigabit Networking Workshop in Conjunction with IEEE INFOCOM, 2001
[26] Khotimsky D, Krishnan S. Stability analysis of a parallel packet switch with bufferless input demultiplexors [C]. In: Proceedings of IEEE ICC 2001. 100-111
[27] Khotimsky D, Krishnan S. Evaluation of open-loop sequence control schemes for multi-path switches [C]. In: Proceedings of IEEE ICC 2002. 2116-2120
[28] Keslassy I. The load-balanced router [PhD Thesis]. Stanford University, 2004.
[29] Oki E, Jing Z, Rojas-Cessa R, Chao H J. Concurrent Round-robin Dispatching Scheme for a Clos-network Switch. In Proceedings of IEEE ICC 2001, pp.107-111,June 2001
[30] Chaney T, Fingerhut J A, Flucke M and Turner J S. Design of a gigabit ATM switch[C]. In: Proc. of IEEE Infocom '97,pp. 1801-1809, April 1997.
[31] Chao H J, Liew S Y, Jing Z. A dual-level matching algorithm for 3-stage Clos-network packet switches [C]. In: Hot Interconnects XI, Stanford, CA, August 2003.
[32] Oki E, Zhigang J, Rojas-Cessa R and Chao H J. Concurrent round-robinbased dispatching schemes for Clos-network switches [J]. IEEE/ACM Transactionson Networking, Vol. 10, No. 6, pp. 830-844, December 2002.
[33] Chang C S, Lee D S, Jou Y S. Load balanced Birkhoff-Von Neumann switches part I: One-stage buffering [J]. Computer Communications, 2002, vol. 25(6): 611-622.
[34] Chang C S, Lee D S, Lien C M. Load balanced Birkhoff-Von Neumann switches part II: Multi-stage buffering [J]. Computer Communications, 2002, vol. 25(6):623-634.
[35] Iyer S, McKeown N. Analysis of the parallel packet switch architecture [J].IEEE/ACM Transactions on Networking, 2003. 314-324
[36]Keslassy I, Chuang S T, Yu K, Miller D, Horowitz M, Solgaard O, McKeown N.Scaling Internet routers using optics [C]. In: ACM SIGCOMM. Karlsruhe,Germany, 2003
[37] Next Generation Networks and the Cisco Carrier Routing System. White Paper,Cisco Systems, 2004. Available at http://www.Cisco.com/warp/public/cc/pd/rt/12000/clc/prodlit/reqng_wp.pdf
[38]Aslam A, Christensen K J. A parallel packet switch with multiplexors containing virtual input queues [J]. Computer Communications 2004, vol. 27: 1248-1263.
[39] Baker F, Requirements for IP Version 4. RFC 1812, June 1995, available at http://www.faqs.org/rfcs/rfcl 812.html.
[40] Bennett J.C.R, Partridge C and Shectman N. Packet reordering is not pathological network behavior [J]. IEEE/ACM Transactions on Networking, Vol. 7, No.6, pp.789-798, December 1999.
[41]Jaiswal S, Iannaccone G, Dior C, Kurose J. Measurement and classification of out-of-sequence packets in a tier-1 IP backbone [C] In: IEEE Infocom '03, San Francisco, CA, 2003.
[42] Fomenkov M, Keys K, Moore D. A longitudinal study of internet traffic from 1998-2001: a view from 20 high performance sites [C]. In: Proc. of WISICT '04,Cancun, Mexico, January 2004.
[43] Blanton E, Allman M. On making TCP more robust to packet reordering [J]. ACM Computer Communication Review, Vol. 32, No. 1, pp. 20-30, January 2002.
[44] Fomenkov M, Keys K. A longitudinal study of internet traffic from 1998-2001: a view from 20 high performance sites [C]. In: Proc. of WISICT '04, Cancun,Mexico, January 2004.
[45] Fraleigh C, Moon S, Lyles B. Packet-level traffic measurements from the Sprint IP backbone [J]. IEEE Network, 2003.
[46] http://www.cidr-report.org/
[47] Hasan J, Vijaykumar T N. Dynamic pipelining: making IP-lookup truly scalable [C]. In: Proc. of SIGCOMM'05, pp. 205-216, August 21-26, 2005, Philadelphia,Pennsylvania, USA.
[48] Jaeggli J. Editorial. http://www.nanog.org/mtg-0702/presentations/fib-editorial.pdf
[49]Nojima S, Tsutio E, Fukuda H, Hashimoto M. Integrated services packet network using bus matrix switch [J]. IEEE J. Sel. Areas in Communications, October 1987,vol. 5(8): 1284-1292.
[50]Singhal V, Le R. High-speed buffered crossbar switch desigh using Virtex-EM devices. Mar. 14,2000.
[51]McKeown N, Mekkittikul A, Anantharam V, Walrand J. Achieving 100% throughput in an input-queued switch [J]. IEEE Transactions on Communications,Aug. 1999, vol. 47(8).
[52] Krishna P, Patel N, Charny A, Simcoe R. On the speedup required for work-conserving crossbar switches [J]. IEEE J. Sel. Areas in Communications,June 1999, vol. 17(6): 1057-1066.
[53] Stephens D, Zhang H. Implementing distributed packet fair queueing in a scalable switch architecture [C]. In: Proc. INFOCOM'98 Conf. San FranCisco,CA, 1998.282-290
[54] Yoshigoe K, Christensen K. A parallel-polled virtual output queued switch with a buffered crossbar [C]. In: Proc. IEEE Workshop High Perf. Switching & Routing (HPSR). Dallas, TX, USA, 2001. 271-275.
[55] Yoshigoe K, Christensen K. An evolution to crossbar switches with buffered cross points [J]. IEEE Network Magazine, September-October 2003: 48-56.
[56] Yoshigoe K, Christensen K, Jacob A. The RR/RR CICQ switch: Hardware design for 10-Gbps link speed [C]. In: Proc. IEEE Int. Performance, Computing, and Communications Conf, April 2003. 481-485.
[57] Katevenis M, Passas G, Simos D, Papaefstathiou I, Chrysos N. Variable packet size buffered crossbar (CICQ) switches [C]. In: IEEE International Conference on Communications (ICC2004), 2004. 1090-1096
[58]Rojas-Cessa R, Oki E. Round robin selection with adaptable size frame in a combined input-crosspoint buffered switch [J]. IEEE Communications Letters, Nov.2003, vol. 7(11).
[59]Rojas-Cessa R, Oki E, Chao H J. CIXOB-k: Combined inputcrosspoint-output buffered packet switch [J]. IEEE GLOBECOM 2001, Nov. 2001: 2654-2660.
[60] Rojas-Cessa R, Oki E, Jing Z, Chao H J. CIXB-1: Combined input one-cell-crosspoint buffered switch [C]. In: IEEE HPSR 2001. Dallas, USA, 2001.324-329.
[61] Chrysos N, Katevenis M. Weighted fairness in buffered crossbar scheduling [C]. In:IEEE HPSR 2003. Torino, Italy, 2003. 17-22
[62]Javidi T, Magill R, Hrabik T. A high-throughput scheduling algorithm for a buffered crossbar switch fabric [C]. In: Proc. IEEE Int. Conf. on Communications(ICC2001). Helsinki, Finland. 1586-1591
[63]Nabeshima M. Performance evaluation of a combined input and crosspoint queued switch [J]. IEICE Trans. Commun., Mar. 2000, vol. E83-B(3).
[64]Mhamdi L, Hamdi M. MCBF: A high-performance scheduling algorithm for buffered crossbar switches [J]. IEEE Communications Letters, Sept. 2003, vol. 7(9):451-453.
[65] Lin X, McKinley P K, Ni L M. The message flow model for routing in wormhole-routed networks [J]. IEEE Trans. on Parallel and Distributed Systems,July 1995, vol. 6(7): 755-760.
[66] Yoshigoe K, Christensen K J. Design and evaluation of a parallel-polled virtual output queued switch [C]. In: Proceedings of the IEEE 2001 International Conference on Communications, 2001. 112-116
[67] Chuang S T, Iyer S, McKeown N. Practical algorithms for performance guarantees in buffered crossbars [C]. In: Proc. INFOCOM'2005 Conf, 2005. 981-991
[68] Chuang S T, Goel A, McKeown N, Prabhakar B. Matching output queueing with a combined input output queued switch [J]. IEEE J. Select. Areas Commun.,A short version appears in The Proceedings of Infocom'99, vol. 17(6): 1030-1039.
[69]Demers A, Keshav S, Shenker S. Analysis and simulation of a fair queuing algorithm [J]. ACM Computer Communication Review, 1989. 3-12.
[70]Parekh A K, Gallager R G. A generalized processor sharing approach to flow control in integrated services networks: The single node case [J]. IEEE/ACM Transaction on Networking, June 1993, vol. 1(3): 344-357.
[71] Iyer S, McKeown N. Making parallel packet switches practical [C]. In: Proc. IEEE INFOCOM,2001. 1680-1687
[72] Chang C S, Lee D S, Shih Y J. Mailbox switch: A scalable two-stage switch architecture for conflict resolution of ordered packets [C]. In: IEEE INFOCOM.Miami, FL, 2004
[73] Lin B, Keslassy I. The concurrent matching switch architecture [C]. In: 25th IEEE INFOCOM. Barcelona, 2006.
[74] Bennett J, Partridge C, Shectman N. Packet reordering is not pathological network behavior [J]. IEEE/ACM Trans. on Networking, 1999, vol. 7(6): 789—798.
[75] Lin B, Keslassy I. A scalable switch for service guarantees [C]. In: Proceedings of the 13th IEEE Symposium on High-Performance Interconnects, 2005.
[76] Chang C S, Chen W J, H. Y. Huang. On service guarantees for input buffered crossbar switches: A capacity decomposition approach by birkhoff and von neumann [C]. In: IEEE IWQoS'99. London, UK, 1999. 79-86.
[77] McKeown N, Anantharan V, J. Walrand. Achieving 100% throughput in an input-queued switch [C]. In: IEEE INFOCOM. San FranCisco, CA, March 1996.296-302.
[78]Giaccone P, Prabhakar B, D. Shah. Randomized scheduling algorithms for input-queued switches[J].IEEE Journal of Selected Areas in Communication,May 2003.642-655.
[79]Li Y,Panwar S,Chao H J.On the performance of a dual round-robin switch[C].In:IEEE INFOCOM,2001.1688-1697.
[80]Leonardi E,Mellia M,Neri F.On the stability of input-queued switches with speed-up[J].IEEE/ACM Transactions on Networking,2001,vol.9(1):104-118.
[81]Dai J G,Prabhakar B.The throughput of data switches with and without speedup [C].In:IEEE INFOCOM.Tel Aviv,Israel,March 2000.556-564
[82]Chiussi F,Khotimsky D,Krishnan S.Generalized inverse multiplexing of switched ATM connections[C].In:Proceedings of IEEE GLOBECOM,1998.3134-3140
[83]Adiseshu H,Parulkar G,Varghese G.Reliable FIFO load balancing over multiple FIFO channels[R]:Washington University Technical Report WUCS-95-11.
[84]Pattavina A.Performance Evaluation of Batcher-Banyan Interconnection Networks with Output Pooling.IEEE J.Selected Areas of Comm.,vol.9,pp.95-103,Jan.1991
[85]Tobagi F,Kwok T,Chiussi F.Architecture,Performance,and Implementation of the Tandem Banyan Fast Packet Switch.IEEE J.Selected Areas in Comm.,vol.9,pp.1173-1193,Oct.1991
[86]Wong P,Yeung M.Design and Analysis of a Novel Fast Packet Switch-Pipeline Banyan.IEEE/ACM Trans.Networking,vol.3,no.1,pp.63-69,Feb.1995
[87]Bassi S,et al.Multistage Shuffle Networks with Shortest Path and Deflection Routing for High Performance ATM Switching:The Open-Loop Shuffleout.IEEE Trans.Comm.,vol.42,pp.2881-2889,Oct.1994
[88]Sapountzis G,Katevenis M.Benes switching fabrics with O(n)-complexity internal backpressure[J].IEEE Communications Magazine,January 2005,vol.43(1):88-94.
[89]Dally W J.Performance analysis of k-ary n-cube interconnection networks[J].IEEE Transactions on Computers,1990,vol.36(9):775-785.
[90]Ould-Khaoua M,Machenzie L M.On the design of hypermesh interconnection networks for multicomputers[J].Journal of Systems Architecture,2000,vol.46:779-792.
[91]Ling L,Filho A.D-arm:A new proposal for multi-dimensional interconnection networks[J].ACM SIGCOMM Computer Communication Review Journal,2001,vol.31(1):33-58.
[92]Chrysos N,Katevenis M.Scheduling in non-blocking buffered three-stage switching fabrics[C].In:25th IEEE INFOCOM.Barcelona,2006
[93]Pappu P.Distributed queueing in scalable high performance routers[C].In:Proceedings of IEEE INFOCOM,2003
[94]Pappu P,Turner J,Wong K.Work-conserving distributed schedulers for terabit routers [C]. In: Proceedings of SIGCOMM, 2004
[95]Pappu P. Distributed queueing in scalable high performance routers [C]. In:Proceedings of IEEE INFOCOM, 2003
[96]Pappu P, Turner J, Wong K. Work-conserving distributed schedulers for terabit routers [C]. In: Proceedings of SIGCOMM, 2004
[97] Dally w j. Scalable switching fabrics for Internet routers. White Paper, Avici Systems, 2002. Available at http://www.Avici.Com/technology/whitepapers/tsrfabric-whitepaper.Pdf
[98] T640 Routing Node and TX Matrix Platform: Architecture. White Paper, Juniper Networks, 2004
[99] Guan J B, Lu X C, Sun Z G. DMR: a Novel Routing Algorithm in 3D Torus Switching Fabric. In: Proceedings of the International Conference on High Performance Computing and Applications (Current Trends in High Performance Computing and its Applications), August 8-10, 2004, Shanghai, P.R. China. Berlin Heidelberg: Springer-Verlag, 2005. 299-303
[100] Tammel A. How to survive as an ISP [C]. In: Proceedings of Networld Interop,1997.
[101] Mathew G. Internet growth summary, 1996. Available at http://www.mit.edu/people/mkgray/net/Internet-growth-summary.html
[102] Blanton E, Allman M. On making TCP more robust to packet reordering [J].ACM Computer Communication Review, Vol. 32, No. 1, pp. 20-30, January 2002.
[ 103] http://klamath.stanford.edu/tools/SIM/
[104] Cuppu V, Jacob B, Davis B. A performance comparison of contemporary DRAM architectures. In: Proc. of the 26th Int. Symp. Computer Architecture (ISCA'99).Atlanta,GA, 1999.222-233.
[105] Bianco A, Giaccone P, Leonardi E, Neri F. A Framework for Differential Frame-based Matching Algorithms in Input-queued Switches. In: Proc. of IEEE INFOCOM. 2004. 1147-1157.
[106] Oki E, Rojas-Cessa R, Chao H J. A Pipeline-based Maximal-sized Matching Scheme for High-speed Input-buffered Switches. IEICE Trans. Commun, July 2002,vol.E85-B(7):1302-1311.
[107] Chang CS, Chen WJ, Huang HY. Birkhoff-von Neumann input buffered crossbar switches [C]. In: Proc. of the IEEE INFOCOM. Tel Aviv: IEEE Communications Society, 2000. 1614-1623.
[108] Iyer S, Awadallah A, McKeown N. Analysis of a packet switch with memories running slower than the line rate. In: Proc. of IEEE INFOCOM. 2000. 529-537.
[109] Cruz R L. A calculus for network delay, Part I: Network Elements in Isolation.IEEE Trans. Inform. Theory, 1991, vol. 37: 114-131.
[110]D E Knuth.计算机程序设计艺术第3卷:排序和查找(第二版)[M].苏运霖,译.北京:国防工业出版社,2003.458-478.
[111]Morrison D R.PATRICIA-pratical algorithm to retrieve information coded in alphanumeric[J].Journal of ACM,1968,15(4):514-534.
[112]Sklower K.A tree-based packet routing table for berkeley unix[A].Proceedings of 1991 Winter USENIX Conference[C].Dallas TX USA:USENIX,1991.93 -99.
[113]Baboescu F,Rajgopal S,Huang L B,Richardson N.Hardware Implementation of a Tree Based IP Lookup Algorithm for OC-768 and beyond[C].In:Proc.DesignCon,2005.1680-1687.
[114]Eatherton W.Hardware-based internet protocol prefix lookups.In Eatherton,Will.Hardware.-Based Internet Protocol Prefix Lookups[MS thesis]Washington University Electrical Engineering Department,may 1999.
[115]Chiueh T,Pradhan P.High performance IP routing table lookup using CPU caching[C]In:Proc.of IEEE INFOCOMM 1999
[116]Degermark M,A Brodnik,Carlsson S,Pink S.Small forwarding tables for fast routing lookups[C]In:Proc.of ACM SIGCOMM '97,Cannes,September 1997.
[117]Merit Inc.IPMA Statistics.http://nic.merit.edu/ipma
[118]Srinivasan V,Varghese G.Fast IP lookups using controlled prefix expansion[J].ACM Transactions on Computer Systems,1999,17(1):1-40.
[119]Nilsson S,Karlsson G.IP address lookup using LC-tries[J].IEEE Journal on Selected Areas in Communications,1999,17(6):1083-1092.
[120]Chiueh T C,Pradhan P.High performance IP routing table lookup using CPU caching[C].In:Proc of IEEE Infocom99,New York USA,1999.1421-1428.
[121]Wang M,Deering S,Hain T,Dunn L.Non-random Generator for IPv6 Tables [C].In:Proc.of 12~(th) Annual IEEE Symposium on High Performance Interconnects,Aug.2004,35-40.
[122]Waldvogel M,Varghese G,Turner J,and Plattner B.Scalable high speed IP routing lookups[J].ACM Transactions on Computer Systems,19(4):440-482,November 2001.
[123]IPv6 Address Allocation and Assignment Policy(RIPE),Available at http://www.ripe.net/ripe/docs/ipv6policy.html.
[124]IPv6 Address Allocation and Assignment Policy(ARIN).Available at http://www.arin.net/policy/ipv6-policy.html.
[125]IPv6 Address Allocation and Assignment Policy(APNIC),Available at http://www.apnic.net/docs/policy/ipv6-address-policy.html.
[126]Deering S,Hinden R,Nordmark E.IPv6 global unicast address format.RFC 3587,Aug.2003.http://www.ietf.org/rfc/rfc3587.txt
[127] http://bgp.potaroo.net/v6/as6447/
[128] Deering S , Hinden R. Internet protocol, Version 6 (IPv6) Specification. RFC 2460, Dec. 1998. http://www.ietf.org/ rfc/ rfc2460. txt.
[129] Hinden R, Deering S. IP Version 6 Addressing Architecture. RFC 4291, Feb.2006. http://www.ietf.org/rfc/rfc4291 .txt
[130] Rekhter Y, Li T. An architecture for IPv6 unicast address allocation. RFC 1887.Dec. 1995. http://www.ietf.org/rfc/rfcl887.txt
[131] IAB, IESG. IAB/IESG Recommendations on IPv6 Address Allocations to Sites.RFC 3177. Sep. 2001. http://www.ietf.org/rfc/rfc3177.txt
[132] Gupta M, Singh S. Greening of the Internet [C]. In: ACM SIGCOMM. Karlsruhe,Germany, 2003
[2]管剑波,苏金树,卢锡城.支持单一POP应用的异构路由器聚合交换技术.国防科学技术大学学报,2005,27(5):13-17
[3]McKeown N.Growth in router capacity.IPAM Workshop,Oct.2003,Lake Arrowhead,CA.Available at http://tiny-tera.stanford.edu/～nickm/talks/index.html
[4]Odlyzko A.M.Comments on the Larry Roberts and Caspian networks study of Internet traffic growth.The Cook Report on the Internet,Dec.2001:12-15
[5]Odlyzko A.M.The current state and likely evolution of the Internet.Proc.of Globecom'99,1999:1869-1875
[6]McKeown N.Internet Routers Past,Present and Future.British Computer Society,June.2006,CA.Available at http://tiny-tera.stanford.edu/～nickm/talks/index.html
[7]Bradner S,McQuaid J.Benchmarking methodology for network interconnect devices.RFC 2544,1999.http://www.ietf.org/rfc/rfc2544.txt
[8]Bradner S,McQuaid J.Benchmarking methodology for network interconnect devices.RFC 2544,1999.http://www.ietf.org/rfc/rfc2544.txt
[9]McKeown N.Scheduling algorithms for input-queued switches[PhD Thesis].University of California,Berkeley,1995.
[10]McKeown N.The iSLIP scheduling algorithm for input-queued switches[J].IEEE/ACM Trans.Networking,Apr.1999,vol.7(2).
[11]Anderson T E,Owicki S S,Saxe J B,Thacker C P.High-speed switch scheduling for local-area networks[J].ACM Transactions on Computer Systems,1999,vol.11(4):319-352.
[12]Marsan M,Bianco A,Leonardi E,Milla L.RPA:A flexible scheduling algorithm for input buffered switches[J].IEEE Transactions on Communications,1999,vol.47(12):1921-1933.
[13]Mekkittikui A,McKeown N.A practical scheduling algorithm to achieve 100%throughput in input-queued switches[C].In:Akyildiz I,ed.Proceedings of the IEEE INFOCOM.San FranCisco,IEEE Communications Society,1998.792-799
[14]Duan H,Lockwood J,Kang S,Will J.A high performance OC12/OC48 queue design prototype for input buffered atm switches[C].In:Hasegawa T,ed.Proceedings of the IEEE INFOCOM.Kobe,IEEE Communications Society,1997.20-28
[15]Iyer S,Kompella R,McKeown N.Analysis of a memory architecture for fast packet buffers[C].In:Proceedings of the IEEE Workshop on High Performance Switching and Routing, 2001. 368-373
[16] Shi L, Liu B, Li W, Wu B, Liu Y. DS-PPS: A practical framework to guarantee differentiated QoS in terabit routers with parallel packet switch [C]. In: 25th IEEE INFOCOM. Barcelona, 2006
[17] Patterson D. and Hennessy J. Computer architecture, a quantitative approach.Morgan Kaufmann, 1996.
[18] Rambus, inc., los altos, ca. [online]. Available: Http://www.Rambus.Com
[19]Rekhter Y, Li T. An architecture for IP address allocation with CIDR. RFC 1518,Sep. 1993. Available at http://www.ietf.org/rfc/rfc1518.txt
[20] Fuller V, Li T, Yu J, Varadhan K. Classless inter-domain routing (CIDR): an address assignment and aggregation strategy. RFC 1519, Sep. 1993. Available at http://www.ietf.org/rfc/rfc1519.txt
[21] Ruiz-Sanchez M, Biersack E, and Dabbous W. Survey and taxonomy of IP address lookup algorithms. IEEE Network, March 2001
[22]Tzeng H, Przygienda T. On fast address-lookup algorithms. IEEE Journal on Selected Areas in Communications, 1999, 17(6):1067-1082.
[23] Aslam A, Christensen K J. A parallel packet switch with multiplexors containing virtual input queues [J]. Computer Communications 2004, vol. 27: 1248-1263.
[24]Mneimneh S, K. Siu. Scheduling unsplittable flows using parallel switches [C]. In:Proceedings of IEEE ICC 2002.2410-2415
[25] Khotimsky D, Krishnan S. Towards the recognition of parallel packet switches [C].In: Proceedings of the Gigabit Networking Workshop in Conjunction with IEEE INFOCOM, 2001
[26] Khotimsky D, Krishnan S. Stability analysis of a parallel packet switch with bufferless input demultiplexors [C]. In: Proceedings of IEEE ICC 2001. 100-111
[27] Khotimsky D, Krishnan S. Evaluation of open-loop sequence control schemes for multi-path switches [C]. In: Proceedings of IEEE ICC 2002. 2116-2120
[28] Keslassy I. The load-balanced router [PhD Thesis]. Stanford University, 2004.
[29] Oki E, Jing Z, Rojas-Cessa R, Chao H J. Concurrent Round-robin Dispatching Scheme for a Clos-network Switch. In Proceedings of IEEE ICC 2001, pp.107-111,June 2001
[30] Chaney T, Fingerhut J A, Flucke M and Turner J S. Design of a gigabit ATM switch[C]. In: Proc. of IEEE Infocom '97,pp. 1801-1809, April 1997.
[31] Chao H J, Liew S Y, Jing Z. A dual-level matching algorithm for 3-stage Clos-network packet switches [C]. In: Hot Interconnects XI, Stanford, CA, August 2003.
[32] Oki E, Zhigang J, Rojas-Cessa R and Chao H J. Concurrent round-robinbased dispatching schemes for Clos-network switches [J]. IEEE/ACM Transactionson Networking, Vol. 10, No. 6, pp. 830-844, December 2002.
[33] Chang C S, Lee D S, Jou Y S. Load balanced Birkhoff-Von Neumann switches part I: One-stage buffering [J]. Computer Communications, 2002, vol. 25(6): 611-622.
[34] Chang C S, Lee D S, Lien C M. Load balanced Birkhoff-Von Neumann switches part II: Multi-stage buffering [J]. Computer Communications, 2002, vol. 25(6):623-634.
[35] Iyer S, McKeown N. Analysis of the parallel packet switch architecture [J].IEEE/ACM Transactions on Networking, 2003. 314-324
[36]Keslassy I, Chuang S T, Yu K, Miller D, Horowitz M, Solgaard O, McKeown N.Scaling Internet routers using optics [C]. In: ACM SIGCOMM. Karlsruhe,Germany, 2003
[37] Next Generation Networks and the Cisco Carrier Routing System. White Paper,Cisco Systems, 2004. Available at http://www.Cisco.com/warp/public/cc/pd/rt/12000/clc/prodlit/reqng_wp.pdf
[38]Aslam A, Christensen K J. A parallel packet switch with multiplexors containing virtual input queues [J]. Computer Communications 2004, vol. 27: 1248-1263.
[39] Baker F, Requirements for IP Version 4. RFC 1812, June 1995, available at http://www.faqs.org/rfcs/rfcl 812.html.
[40] Bennett J.C.R, Partridge C and Shectman N. Packet reordering is not pathological network behavior [J]. IEEE/ACM Transactions on Networking, Vol. 7, No.6, pp.789-798, December 1999.
[41]Jaiswal S, Iannaccone G, Dior C, Kurose J. Measurement and classification of out-of-sequence packets in a tier-1 IP backbone [C] In: IEEE Infocom '03, San Francisco, CA, 2003.
[42] Fomenkov M, Keys K, Moore D. A longitudinal study of internet traffic from 1998-2001: a view from 20 high performance sites [C]. In: Proc. of WISICT '04,Cancun, Mexico, January 2004.
[43] Blanton E, Allman M. On making TCP more robust to packet reordering [J]. ACM Computer Communication Review, Vol. 32, No. 1, pp. 20-30, January 2002.
[44] Fomenkov M, Keys K. A longitudinal study of internet traffic from 1998-2001: a view from 20 high performance sites [C]. In: Proc. of WISICT '04, Cancun,Mexico, January 2004.
[45] Fraleigh C, Moon S, Lyles B. Packet-level traffic measurements from the Sprint IP backbone [J]. IEEE Network, 2003.
[46] http://www.cidr-report.org/
[47] Hasan J, Vijaykumar T N. Dynamic pipelining: making IP-lookup truly scalable [C]. In: Proc. of SIGCOMM'05, pp. 205-216, August 21-26, 2005, Philadelphia,Pennsylvania, USA.
[48] Jaeggli J. Editorial. http://www.nanog.org/mtg-0702/presentations/fib-editorial.pdf
[49]Nojima S, Tsutio E, Fukuda H, Hashimoto M. Integrated services packet network using bus matrix switch [J]. IEEE J. Sel. Areas in Communications, October 1987,vol. 5(8): 1284-1292.
[50]Singhal V, Le R. High-speed buffered crossbar switch desigh using Virtex-EM devices. Mar. 14,2000.
[51]McKeown N, Mekkittikul A, Anantharam V, Walrand J. Achieving 100% throughput in an input-queued switch [J]. IEEE Transactions on Communications,Aug. 1999, vol. 47(8).
[52] Krishna P, Patel N, Charny A, Simcoe R. On the speedup required for work-conserving crossbar switches [J]. IEEE J. Sel. Areas in Communications,June 1999, vol. 17(6): 1057-1066.
[53] Stephens D, Zhang H. Implementing distributed packet fair queueing in a scalable switch architecture [C]. In: Proc. INFOCOM'98 Conf. San FranCisco,CA, 1998.282-290
[54] Yoshigoe K, Christensen K. A parallel-polled virtual output queued switch with a buffered crossbar [C]. In: Proc. IEEE Workshop High Perf. Switching & Routing (HPSR). Dallas, TX, USA, 2001. 271-275.
[55] Yoshigoe K, Christensen K. An evolution to crossbar switches with buffered cross points [J]. IEEE Network Magazine, September-October 2003: 48-56.
[56] Yoshigoe K, Christensen K, Jacob A. The RR/RR CICQ switch: Hardware design for 10-Gbps link speed [C]. In: Proc. IEEE Int. Performance, Computing, and Communications Conf, April 2003. 481-485.
[57] Katevenis M, Passas G, Simos D, Papaefstathiou I, Chrysos N. Variable packet size buffered crossbar (CICQ) switches [C]. In: IEEE International Conference on Communications (ICC2004), 2004. 1090-1096
[58]Rojas-Cessa R, Oki E. Round robin selection with adaptable size frame in a combined input-crosspoint buffered switch [J]. IEEE Communications Letters, Nov.2003, vol. 7(11).
[59]Rojas-Cessa R, Oki E, Chao H J. CIXOB-k: Combined inputcrosspoint-output buffered packet switch [J]. IEEE GLOBECOM 2001, Nov. 2001: 2654-2660.
[60] Rojas-Cessa R, Oki E, Jing Z, Chao H J. CIXB-1: Combined input one-cell-crosspoint buffered switch [C]. In: IEEE HPSR 2001. Dallas, USA, 2001.324-329.
[61] Chrysos N, Katevenis M. Weighted fairness in buffered crossbar scheduling [C]. In:IEEE HPSR 2003. Torino, Italy, 2003. 17-22
[62]Javidi T, Magill R, Hrabik T. A high-throughput scheduling algorithm for a buffered crossbar switch fabric [C]. In: Proc. IEEE Int. Conf. on Communications(ICC2001). Helsinki, Finland. 1586-1591
[63]Nabeshima M. Performance evaluation of a combined input and crosspoint queued switch [J]. IEICE Trans. Commun., Mar. 2000, vol. E83-B(3).
[64]Mhamdi L, Hamdi M. MCBF: A high-performance scheduling algorithm for buffered crossbar switches [J]. IEEE Communications Letters, Sept. 2003, vol. 7(9):451-453.
[65] Lin X, McKinley P K, Ni L M. The message flow model for routing in wormhole-routed networks [J]. IEEE Trans. on Parallel and Distributed Systems,July 1995, vol. 6(7): 755-760.
[66] Yoshigoe K, Christensen K J. Design and evaluation of a parallel-polled virtual output queued switch [C]. In: Proceedings of the IEEE 2001 International Conference on Communications, 2001. 112-116
[67] Chuang S T, Iyer S, McKeown N. Practical algorithms for performance guarantees in buffered crossbars [C]. In: Proc. INFOCOM'2005 Conf, 2005. 981-991
[68] Chuang S T, Goel A, McKeown N, Prabhakar B. Matching output queueing with a combined input output queued switch [J]. IEEE J. Select. Areas Commun.,A short version appears in The Proceedings of Infocom'99, vol. 17(6): 1030-1039.
[69]Demers A, Keshav S, Shenker S. Analysis and simulation of a fair queuing algorithm [J]. ACM Computer Communication Review, 1989. 3-12.
[70]Parekh A K, Gallager R G. A generalized processor sharing approach to flow control in integrated services networks: The single node case [J]. IEEE/ACM Transaction on Networking, June 1993, vol. 1(3): 344-357.
[71] Iyer S, McKeown N. Making parallel packet switches practical [C]. In: Proc. IEEE INFOCOM,2001. 1680-1687
[72] Chang C S, Lee D S, Shih Y J. Mailbox switch: A scalable two-stage switch architecture for conflict resolution of ordered packets [C]. In: IEEE INFOCOM.Miami, FL, 2004
[73] Lin B, Keslassy I. The concurrent matching switch architecture [C]. In: 25th IEEE INFOCOM. Barcelona, 2006.
[74] Bennett J, Partridge C, Shectman N. Packet reordering is not pathological network behavior [J]. IEEE/ACM Trans. on Networking, 1999, vol. 7(6): 789—798.
[75] Lin B, Keslassy I. A scalable switch for service guarantees [C]. In: Proceedings of the 13th IEEE Symposium on High-Performance Interconnects, 2005.
[76] Chang C S, Chen W J, H. Y. Huang. On service guarantees for input buffered crossbar switches: A capacity decomposition approach by birkhoff and von neumann [C]. In: IEEE IWQoS'99. London, UK, 1999. 79-86.
[77] McKeown N, Anantharan V, J. Walrand. Achieving 100% throughput in an input-queued switch [C]. In: IEEE INFOCOM. San FranCisco, CA, March 1996.296-302.
[78]Giaccone P, Prabhakar B, D. Shah. Randomized scheduling algorithms for input-queued switches[J].IEEE Journal of Selected Areas in Communication,May 2003.642-655.
[79]Li Y,Panwar S,Chao H J.On the performance of a dual round-robin switch[C].In:IEEE INFOCOM,2001.1688-1697.
[80]Leonardi E,Mellia M,Neri F.On the stability of input-queued switches with speed-up[J].IEEE/ACM Transactions on Networking,2001,vol.9(1):104-118.
[81]Dai J G,Prabhakar B.The throughput of data switches with and without speedup [C].In:IEEE INFOCOM.Tel Aviv,Israel,March 2000.556-564
[82]Chiussi F,Khotimsky D,Krishnan S.Generalized inverse multiplexing of switched ATM connections[C].In:Proceedings of IEEE GLOBECOM,1998.3134-3140
[83]Adiseshu H,Parulkar G,Varghese G.Reliable FIFO load balancing over multiple FIFO channels[R]:Washington University Technical Report WUCS-95-11.
[84]Pattavina A.Performance Evaluation of Batcher-Banyan Interconnection Networks with Output Pooling.IEEE J.Selected Areas of Comm.,vol.9,pp.95-103,Jan.1991
[85]Tobagi F,Kwok T,Chiussi F.Architecture,Performance,and Implementation of the Tandem Banyan Fast Packet Switch.IEEE J.Selected Areas in Comm.,vol.9,pp.1173-1193,Oct.1991
[86]Wong P,Yeung M.Design and Analysis of a Novel Fast Packet Switch-Pipeline Banyan.IEEE/ACM Trans.Networking,vol.3,no.1,pp.63-69,Feb.1995
[87]Bassi S,et al.Multistage Shuffle Networks with Shortest Path and Deflection Routing for High Performance ATM Switching:The Open-Loop Shuffleout.IEEE Trans.Comm.,vol.42,pp.2881-2889,Oct.1994
[88]Sapountzis G,Katevenis M.Benes switching fabrics with O(n)-complexity internal backpressure[J].IEEE Communications Magazine,January 2005,vol.43(1):88-94.
[89]Dally W J.Performance analysis of k-ary n-cube interconnection networks[J].IEEE Transactions on Computers,1990,vol.36(9):775-785.
[90]Ould-Khaoua M,Machenzie L M.On the design of hypermesh interconnection networks for multicomputers[J].Journal of Systems Architecture,2000,vol.46:779-792.
[91]Ling L,Filho A.D-arm:A new proposal for multi-dimensional interconnection networks[J].ACM SIGCOMM Computer Communication Review Journal,2001,vol.31(1):33-58.
[92]Chrysos N,Katevenis M.Scheduling in non-blocking buffered three-stage switching fabrics[C].In:25th IEEE INFOCOM.Barcelona,2006
[93]Pappu P.Distributed queueing in scalable high performance routers[C].In:Proceedings of IEEE INFOCOM,2003
[94]Pappu P,Turner J,Wong K.Work-conserving distributed schedulers for terabit routers [C]. In: Proceedings of SIGCOMM, 2004
[95]Pappu P. Distributed queueing in scalable high performance routers [C]. In:Proceedings of IEEE INFOCOM, 2003
[96]Pappu P, Turner J, Wong K. Work-conserving distributed schedulers for terabit routers [C]. In: Proceedings of SIGCOMM, 2004
[97] Dally w j. Scalable switching fabrics for Internet routers. White Paper, Avici Systems, 2002. Available at http://www.Avici.Com/technology/whitepapers/tsrfabric-whitepaper.Pdf
[98] T640 Routing Node and TX Matrix Platform: Architecture. White Paper, Juniper Networks, 2004
[99] Guan J B, Lu X C, Sun Z G. DMR: a Novel Routing Algorithm in 3D Torus Switching Fabric. In: Proceedings of the International Conference on High Performance Computing and Applications (Current Trends in High Performance Computing and its Applications), August 8-10, 2004, Shanghai, P.R. China. Berlin Heidelberg: Springer-Verlag, 2005. 299-303
[100] Tammel A. How to survive as an ISP [C]. In: Proceedings of Networld Interop,1997.
[101] Mathew G. Internet growth summary, 1996. Available at http://www.mit.edu/people/mkgray/net/Internet-growth-summary.html
[102] Blanton E, Allman M. On making TCP more robust to packet reordering [J].ACM Computer Communication Review, Vol. 32, No. 1, pp. 20-30, January 2002.
[ 103] http://klamath.stanford.edu/tools/SIM/
[104] Cuppu V, Jacob B, Davis B. A performance comparison of contemporary DRAM architectures. In: Proc. of the 26th Int. Symp. Computer Architecture (ISCA'99).Atlanta,GA, 1999.222-233.
[105] Bianco A, Giaccone P, Leonardi E, Neri F. A Framework for Differential Frame-based Matching Algorithms in Input-queued Switches. In: Proc. of IEEE INFOCOM. 2004. 1147-1157.
[106] Oki E, Rojas-Cessa R, Chao H J. A Pipeline-based Maximal-sized Matching Scheme for High-speed Input-buffered Switches. IEICE Trans. Commun, July 2002,vol.E85-B(7):1302-1311.
[107] Chang CS, Chen WJ, Huang HY. Birkhoff-von Neumann input buffered crossbar switches [C]. In: Proc. of the IEEE INFOCOM. Tel Aviv: IEEE Communications Society, 2000. 1614-1623.
[108] Iyer S, Awadallah A, McKeown N. Analysis of a packet switch with memories running slower than the line rate. In: Proc. of IEEE INFOCOM. 2000. 529-537.
[109] Cruz R L. A calculus for network delay, Part I: Network Elements in Isolation.IEEE Trans. Inform. Theory, 1991, vol. 37: 114-131.
[110]D E Knuth.计算机程序设计艺术第3卷:排序和查找(第二版)[M].苏运霖,译.北京:国防工业出版社,2003.458-478.
[111]Morrison D R.PATRICIA-pratical algorithm to retrieve information coded in alphanumeric[J].Journal of ACM,1968,15(4):514-534.
[112]Sklower K.A tree-based packet routing table for berkeley unix[A].Proceedings of 1991 Winter USENIX Conference[C].Dallas TX USA:USENIX,1991.93 -99.
[113]Baboescu F,Rajgopal S,Huang L B,Richardson N.Hardware Implementation of a Tree Based IP Lookup Algorithm for OC-768 and beyond[C].In:Proc.DesignCon,2005.1680-1687.
[114]Eatherton W.Hardware-based internet protocol prefix lookups.In Eatherton,Will.Hardware.-Based Internet Protocol Prefix Lookups[MS thesis]Washington University Electrical Engineering Department,may 1999.
[115]Chiueh T,Pradhan P.High performance IP routing table lookup using CPU caching[C]In:Proc.of IEEE INFOCOMM 1999
[116]Degermark M,A Brodnik,Carlsson S,Pink S.Small forwarding tables for fast routing lookups[C]In:Proc.of ACM SIGCOMM '97,Cannes,September 1997.
[117]Merit Inc.IPMA Statistics.http://nic.merit.edu/ipma
[118]Srinivasan V,Varghese G.Fast IP lookups using controlled prefix expansion[J].ACM Transactions on Computer Systems,1999,17(1):1-40.
[119]Nilsson S,Karlsson G.IP address lookup using LC-tries[J].IEEE Journal on Selected Areas in Communications,1999,17(6):1083-1092.
[120]Chiueh T C,Pradhan P.High performance IP routing table lookup using CPU caching[C].In:Proc of IEEE Infocom99,New York USA,1999.1421-1428.
[121]Wang M,Deering S,Hain T,Dunn L.Non-random Generator for IPv6 Tables [C].In:Proc.of 12~(th) Annual IEEE Symposium on High Performance Interconnects,Aug.2004,35-40.
[122]Waldvogel M,Varghese G,Turner J,and Plattner B.Scalable high speed IP routing lookups[J].ACM Transactions on Computer Systems,19(4):440-482,November 2001.
[123]IPv6 Address Allocation and Assignment Policy(RIPE),Available at http://www.ripe.net/ripe/docs/ipv6policy.html.
[124]IPv6 Address Allocation and Assignment Policy(ARIN).Available at http://www.arin.net/policy/ipv6-policy.html.
[125]IPv6 Address Allocation and Assignment Policy(APNIC),Available at http://www.apnic.net/docs/policy/ipv6-address-policy.html.
[126]Deering S,Hinden R,Nordmark E.IPv6 global unicast address format.RFC 3587,Aug.2003.http://www.ietf.org/rfc/rfc3587.txt
[127] http://bgp.potaroo.net/v6/as6447/
[128] Deering S , Hinden R. Internet protocol, Version 6 (IPv6) Specification. RFC 2460, Dec. 1998. http://www.ietf.org/ rfc/ rfc2460. txt.
[129] Hinden R, Deering S. IP Version 6 Addressing Architecture. RFC 4291, Feb.2006. http://www.ietf.org/rfc/rfc4291 .txt
[130] Rekhter Y, Li T. An architecture for IPv6 unicast address allocation. RFC 1887.Dec. 1995. http://www.ietf.org/rfc/rfcl887.txt
[131] IAB, IESG. IAB/IESG Recommendations on IPv6 Address Allocations to Sites.RFC 3177. Sep. 2001. http://www.ietf.org/rfc/rfc3177.txt
[132] Gupta M, Singh S. Greening of the Internet [C]. In: ACM SIGCOMM. Karlsruhe,Germany, 2003