高速多级分组交换网络若干关键技术的研究
|
摘要
随着Internet业务爆炸式增长和光宽带传输技术的迅猛发展,网络结点逐渐成为网络宽带化的瓶颈。路由器(交换机)的内部交换网络作为网络结点的核心部件,是目前高性能宽带信息网络研究的热点之一。单Crossbar交换网络是目前核心路由器的主流交换结构,其研究成果十分丰富,但是,由于受工程实现的限制(机架供电、芯片体积等),单Crossbar交换网络容量无法做到很大。采用多级交换结构是构建大容量分组交换网络的常用途径。直接连接网络和间接连接网络是空分多级交换网络的两种主要拓扑类型。直接连接网络虽然具有良好的可扩展性,但是网络性能难以控制,只是在大容量分组交换网络研究初期得到应用;间接连接网络是目前多级分组交换网络研究的重点。目前对多级间接连接网络(如三级Clos网络,并行分组交换和两级交换网络等)的研究是对单Crossbar交换网络研究的简单推广,从本质上说是一种集中式控制方式,这种方式会带来调度算法实现困难,交换网络性能难以控制和无法充分发挥多级交换网络拓扑优势等问题,本文针对这些问题对多级高速间接连接分组交换网络的若干关键技术进行了研究,主要工作和贡献如下:
1.提出了多级间接分组交换网络分布式调度思想。按照交换网络各级交换单元在网络中的地位不同,将它们分为负载均匀级交换单元和调度级交换单元,分别通过负载均衡策略和交换单元内部调度策略来实现交换控制。这样将多级间接连接网络的调度问题分解为负载均衡和交换单元内部的调度两个子问题来处理,带来了以下优点:(1)实现了调度算法的完全分布式,便于多机架实现。由于在分布式调度思想中,通过负载均衡级来协调调度级交换单元的业务负载,不需要在交换网络的各级和级内交换单元间进行控制信息的交换,因此,这种调度算法是完全分布式的;(2)调度算法具有良好的继承性。在分布式调度多级间接连接分组交换网络中,调度级交换单元的调度就是单Crossbar内部的调度,可以完全借鉴现有单Crossbar交换网络的研究成果;(3)算法实现简单,算法性能便于控制和分析。
2.分析了三级Clos网络分布式调度保证性能的资源需求。研究表明在三级Clos网络分布式调度中,保证性能的网络资源需求是Clos网络保证性能的最少资源。信元乱序是三级Clos网络分布式调度采用定长信元机制面临的主要问题之一,本文提出了一种可以实现信元保序的三级Clos网络分布式调度调度算法——LDVSA算法,通过分析表明该算法不仅具有较好的性能同时可以实现分组信元的完全保序。
3.本文在一种实现简单的分布式调度算法——RRBSA算法下,对三级Clos网络分布式调度的交换机制进行了研究。研究表明,定长信元交换机制和变长分组交换机制在三级Clos网络分布式调度中都具有一定的局限性,为此,本文提出了一种结合定长信元和变长分组交换机制优势的混合交换机制。这种交换机制以变长分组为单位实现负载均衡,解决了信元乱序问题;通过采用一种新型的令牌机制实现了变长分组负载分配的公平性;在Clos网络的后两级采用定长信元交换机制,获得了良好的业务适应性,研究表明混合交换机制是一种适合三级Clos网络分布式调度的交换机制。
4.对三级Clos网络的故障进行了分析,提出了三级Clos网络分布式调度的故障模型,通过将网络故障归结为对输入级不同队列的影响,提出了三级Clos网络分布式调度的容错算法。对算法的容错方式、容错能力进行了分析,研究表明,该算法具有较好的容错能力。
5.将分布式调度思想应用到目前研究较多的两种多级交换网络结构——并行分组交换(PPS)和两级交换网络中,克服了这两种交换网络现有研究的不足。在两级交换网络中实现了在分布式调度思想下和三级Clos网络的统一,使得三级Clos网络分布式调度算法得到进一步简化。利用本文的研究成果构建超大(100Tb/s以上)容量分组交换网络,可以在现有成熟技术下实现最大容量为655.36Tb/s的交换网络,远远高于现有研究成果的水平。
6.提出了一种具有良好可扩展性的交换网络拓扑结构——MR网络。该网络通过在交换网络中间级引入具有直接连接网络特点的环形网络和巧妙的级间连接关系,克服了传统间接连接网络可扩展性的不足。
With the explosive growth of Internet traffic and the rapid development of broadband optical transmission technologies, network nodes have gradually become a bottleneck in Internet development. Switch fabric, as the core component of a node, has been becoming one of hotspots in network research . Single-stage crossbar, as the dominating switch fabric in core routers, is quite abundant in its research achievements.However, because of engineering constraints (rack power supply, chip size, etc.), it is not easy to achieve a large switch capacity. To build large-capacity packet switching networks, multi-stage switch fabric is a commonly used means. Direct interconnection network and indirect interconnection network are two main topologies of space-division multi-stage switch fabric. Although direct interconnection networks possess good scalability, their unpredictable performance limits them only available in the early days of large-capacity router research. Indirect interconnection networks are becoming the research focus. The current research methods for indirect interconnection networks (such as three-stage clos networks, parallel packet switch (PPS), two-stage switch network, etc) in literatures are simple extension from those for single-stage crossbar, which are centralized control methods in essentce. These methods have problems of their own, such as difficulty in realization, unpredictable performance, and not full availability of predominance in topology of multi-stage switch fabric, etc. In this thesis we investigate the key technologies of high-speed packet switching multi-stage indirect interconnection networks to try to resolve the problems mentioned above. The main work and contributions are as follows.
1. Distributed scheduling scheme in multi-stage switch faric is proposed.According to different roles of switch units in multi-stage switch fabrics, they are divided into load balancing stage of units and scheduling stage of units within which the control on switch is achieved through load balancing strategy and scheduling strategy respectively. Therefore, the scheduling problem of multi-stage indirect interconnection networks is decomposed into two subproblems of load balancing and scheduling within switch units, thus it has the following advantages: (1) the realization of a fully distributed algorithm makes it convenient for multi-rack implementation. The control information exchange between stages of switch units and between ones within each stage of switch unit is avoided because the traffic load within scheduling stage of switch units is coordinated through the load balancing stage of switch units in distributed scheduling scheme. (2) This scheme has a good inheritance. In our distributed scheduling scheme proposed, the scheduling within scheduling stage of switch units is similar to the one within single-crossbar switch fabrics, and therefore the research results of single-crossbar switch fabric available can be directly used for reference. (3)This scheme is simple in implementation and convenient for algorithm performance analyses and control. .
2. The resource requirements of guaranteeing performance in the distributed scheduling in three-stage Clos networks are analyzed. It is shown that they are the least resource demand. The out-of-sequence of cells is one of primary problems that distributed scheduling in three-stage Clos networks may be confronted with. A new distributed scheduling algorithm called LDVSA (Load Dispatched and Volleyed Scheduling Algorithm) is proposed. Further analysis shows that the algorithm can keep cells in sequence and also possess good performance.
3. Based on a simple distributed scheduling algorithm called RRBSA(Round-Robin Balanced Scheduling Algorithm), switching mechanisms of distributed scheduling in three-stage Clos networks have been studied. The research results show that both fixed length cell switching mechanism and variable length packet switching mechanism have their own limitations. So we propose a new mixed switching mechanism which combines the advantages of the two switching mechanisms mentioned above. The mixed mechanism achieves load balancing on a granularity of variable length packet thus keeping cells in sequence, on the basis of which a new token scheme is adopted to guarantee the fairness of load balancing. In addition, fixed length cell is employed in the later two stages of Clos networks to accommodate various types of traffic. Final results indicate that the mixed switching mechanism is proper for the distributed scheduling in three-stage Clos networks.
4. After the analysis of various faults of three-stage Clos networks, a fault model suitable for distributed scheduling in three-stage Clos networks is presented. Also, according to the affects of network faults on different input queues in input stages, a new distributed fault tolerance scheduling algorithm is put forward. At the same time, its method and capability of fault tolerance are analyzed. Results indicate that the algorithm has good fault-tolerance performance.
5.Distributed scheduling scheme is introduced into two kinds of multi-stage switch fabrics having been received many studies, including PPS(Parallel Packet Switching) and two-stage switch fabric, and thus their research deficiencies are overcome. The distributed scheduling algorithms in three-stage Clos networks are further simplified due to the unification of two-stage networks and three-stage Clos networks under distributed scheduling scheme. Using the study achievements in this thesis to build switch networks with ultra-large capacity (over 100Tb/s) can realize a switch fabric whose maximum capacity reaches up to 655.36Tb/s, much higher than the level of existing research results.
6. A new type of switch fabric called MR (Magic Ring) is proposed. The fabric is a new three-stage indirect interconnection network with good scalability. With the introduction of ring network having the characteristics of direct interconnection networks in middle stage of switch network and of subtle connection relations between stages of switch networks, the new fabric overcomes the weakness in scalability of traditional indirect interconnection networks.
1.提出了多级间接分组交换网络分布式调度思想。按照交换网络各级交换单元在网络中的地位不同,将它们分为负载均匀级交换单元和调度级交换单元,分别通过负载均衡策略和交换单元内部调度策略来实现交换控制。这样将多级间接连接网络的调度问题分解为负载均衡和交换单元内部的调度两个子问题来处理,带来了以下优点:(1)实现了调度算法的完全分布式,便于多机架实现。由于在分布式调度思想中,通过负载均衡级来协调调度级交换单元的业务负载,不需要在交换网络的各级和级内交换单元间进行控制信息的交换,因此,这种调度算法是完全分布式的;(2)调度算法具有良好的继承性。在分布式调度多级间接连接分组交换网络中,调度级交换单元的调度就是单Crossbar内部的调度,可以完全借鉴现有单Crossbar交换网络的研究成果;(3)算法实现简单,算法性能便于控制和分析。
2.分析了三级Clos网络分布式调度保证性能的资源需求。研究表明在三级Clos网络分布式调度中,保证性能的网络资源需求是Clos网络保证性能的最少资源。信元乱序是三级Clos网络分布式调度采用定长信元机制面临的主要问题之一,本文提出了一种可以实现信元保序的三级Clos网络分布式调度调度算法——LDVSA算法,通过分析表明该算法不仅具有较好的性能同时可以实现分组信元的完全保序。
3.本文在一种实现简单的分布式调度算法——RRBSA算法下,对三级Clos网络分布式调度的交换机制进行了研究。研究表明,定长信元交换机制和变长分组交换机制在三级Clos网络分布式调度中都具有一定的局限性,为此,本文提出了一种结合定长信元和变长分组交换机制优势的混合交换机制。这种交换机制以变长分组为单位实现负载均衡,解决了信元乱序问题;通过采用一种新型的令牌机制实现了变长分组负载分配的公平性;在Clos网络的后两级采用定长信元交换机制,获得了良好的业务适应性,研究表明混合交换机制是一种适合三级Clos网络分布式调度的交换机制。
4.对三级Clos网络的故障进行了分析,提出了三级Clos网络分布式调度的故障模型,通过将网络故障归结为对输入级不同队列的影响,提出了三级Clos网络分布式调度的容错算法。对算法的容错方式、容错能力进行了分析,研究表明,该算法具有较好的容错能力。
5.将分布式调度思想应用到目前研究较多的两种多级交换网络结构——并行分组交换(PPS)和两级交换网络中,克服了这两种交换网络现有研究的不足。在两级交换网络中实现了在分布式调度思想下和三级Clos网络的统一,使得三级Clos网络分布式调度算法得到进一步简化。利用本文的研究成果构建超大(100Tb/s以上)容量分组交换网络,可以在现有成熟技术下实现最大容量为655.36Tb/s的交换网络,远远高于现有研究成果的水平。
6.提出了一种具有良好可扩展性的交换网络拓扑结构——MR网络。该网络通过在交换网络中间级引入具有直接连接网络特点的环形网络和巧妙的级间连接关系,克服了传统间接连接网络可扩展性的不足。
With the explosive growth of Internet traffic and the rapid development of broadband optical transmission technologies, network nodes have gradually become a bottleneck in Internet development. Switch fabric, as the core component of a node, has been becoming one of hotspots in network research . Single-stage crossbar, as the dominating switch fabric in core routers, is quite abundant in its research achievements.However, because of engineering constraints (rack power supply, chip size, etc.), it is not easy to achieve a large switch capacity. To build large-capacity packet switching networks, multi-stage switch fabric is a commonly used means. Direct interconnection network and indirect interconnection network are two main topologies of space-division multi-stage switch fabric. Although direct interconnection networks possess good scalability, their unpredictable performance limits them only available in the early days of large-capacity router research. Indirect interconnection networks are becoming the research focus. The current research methods for indirect interconnection networks (such as three-stage clos networks, parallel packet switch (PPS), two-stage switch network, etc) in literatures are simple extension from those for single-stage crossbar, which are centralized control methods in essentce. These methods have problems of their own, such as difficulty in realization, unpredictable performance, and not full availability of predominance in topology of multi-stage switch fabric, etc. In this thesis we investigate the key technologies of high-speed packet switching multi-stage indirect interconnection networks to try to resolve the problems mentioned above. The main work and contributions are as follows.
1. Distributed scheduling scheme in multi-stage switch faric is proposed.According to different roles of switch units in multi-stage switch fabrics, they are divided into load balancing stage of units and scheduling stage of units within which the control on switch is achieved through load balancing strategy and scheduling strategy respectively. Therefore, the scheduling problem of multi-stage indirect interconnection networks is decomposed into two subproblems of load balancing and scheduling within switch units, thus it has the following advantages: (1) the realization of a fully distributed algorithm makes it convenient for multi-rack implementation. The control information exchange between stages of switch units and between ones within each stage of switch unit is avoided because the traffic load within scheduling stage of switch units is coordinated through the load balancing stage of switch units in distributed scheduling scheme. (2) This scheme has a good inheritance. In our distributed scheduling scheme proposed, the scheduling within scheduling stage of switch units is similar to the one within single-crossbar switch fabrics, and therefore the research results of single-crossbar switch fabric available can be directly used for reference. (3)This scheme is simple in implementation and convenient for algorithm performance analyses and control. .
2. The resource requirements of guaranteeing performance in the distributed scheduling in three-stage Clos networks are analyzed. It is shown that they are the least resource demand. The out-of-sequence of cells is one of primary problems that distributed scheduling in three-stage Clos networks may be confronted with. A new distributed scheduling algorithm called LDVSA (Load Dispatched and Volleyed Scheduling Algorithm) is proposed. Further analysis shows that the algorithm can keep cells in sequence and also possess good performance.
3. Based on a simple distributed scheduling algorithm called RRBSA(Round-Robin Balanced Scheduling Algorithm), switching mechanisms of distributed scheduling in three-stage Clos networks have been studied. The research results show that both fixed length cell switching mechanism and variable length packet switching mechanism have their own limitations. So we propose a new mixed switching mechanism which combines the advantages of the two switching mechanisms mentioned above. The mixed mechanism achieves load balancing on a granularity of variable length packet thus keeping cells in sequence, on the basis of which a new token scheme is adopted to guarantee the fairness of load balancing. In addition, fixed length cell is employed in the later two stages of Clos networks to accommodate various types of traffic. Final results indicate that the mixed switching mechanism is proper for the distributed scheduling in three-stage Clos networks.
4. After the analysis of various faults of three-stage Clos networks, a fault model suitable for distributed scheduling in three-stage Clos networks is presented. Also, according to the affects of network faults on different input queues in input stages, a new distributed fault tolerance scheduling algorithm is put forward. At the same time, its method and capability of fault tolerance are analyzed. Results indicate that the algorithm has good fault-tolerance performance.
5.Distributed scheduling scheme is introduced into two kinds of multi-stage switch fabrics having been received many studies, including PPS(Parallel Packet Switching) and two-stage switch fabric, and thus their research deficiencies are overcome. The distributed scheduling algorithms in three-stage Clos networks are further simplified due to the unification of two-stage networks and three-stage Clos networks under distributed scheduling scheme. Using the study achievements in this thesis to build switch networks with ultra-large capacity (over 100Tb/s) can realize a switch fabric whose maximum capacity reaches up to 655.36Tb/s, much higher than the level of existing research results.
6. A new type of switch fabric called MR (Magic Ring) is proposed. The fabric is a new three-stage indirect interconnection network with good scalability. With the introduction of ring network having the characteristics of direct interconnection networks in middle stage of switch network and of subtle connection relations between stages of switch networks, the new fabric overcomes the weakness in scalability of traditional indirect interconnection networks.
引文
[1] Internet growth statistics,http://www.internetworldstats.com/emarketing.htm.
[2] 中 国 互 联 网 络 发 展 状 况 统 计 报 ,http://www.cnnic.cn/uploadfiles/doc /2007/7/18/ .doc
[3] What will high perfermence switches and routers look like in ten years.http://www.tlc-networks.polito.it/hpsr 2003.
[4] A. M. Odlyzko.Internet traffic growth: Sources and implications. Optical Transmission Systems and Equipment for WDM Networking II, B. B. Dingel, W. Weiershausen, A. K. Dutta, and K.-I. Sato, eds., Proc. SPIE, vol. 5247, 2003, pp. 1-15. availabile http://www.dtc.umn.edu/~odlyzko/doc/networks.html.
[5] A. M. Odlyzko .Comments on the Larry Roberts and Caspian Networks study of Internet traffic growth. The Cook Report on the Internet, Dec. 2001, pp. 12-15.
[6] K. G. Coffman, A. M. Odlyzko. Growth of the Internet. In Optical Fiber Telecommunications IV B: Systems and Impairments, I. P. Kaminow and T. Li, eds. Academic Press, 2002, pp. 17-56.
[7] K. Fukuchi. 10.92Tbit/s(273x40 Gbit/s) triple-band/ultra-dense WDM optical repeated transmission experiment. in Proc. OFC2001, PD24, 2001
[8] S. Bigo, Y. Frignac, G. Charlet, et al. 10.2 Tbit/s (256x42.7 Gbit/s PDM/WDM) transmission over 100 km Teralight TM fiber with 1.28 bit/s Hz spectral efficiency. OFC’2001 Technical Digest, Anaheim, California USA, PD25.
[9] Fabio M.Chiussi, Andrea Francini. Scalable Electronic Packet Switches.IEEE Journal on Selected Areas in Communication, 2003,Vol.21(4):486-500.
[10] 刘增基,鲍民权,邱智亮,交换原理与技术,人民邮电出版社,2007 年 9月.
[11] 3G 及 下 一 代 网 络 建 设 : 带 动 高 端 路 由 器 市 场 发 展 的 火 车 头http://www.ccwresearch.com.cn/store/article_content.asp?articleId=4461.
[12] Fuller,V., Li, T., et al. Classless Inter-domain Routing (CIDR): an Address Assignment and Aggregation Strategy. RFC1519,1993
[13] A. Brodnik, S. Carlsson, M. Degermark,et al.Small Forwarding Tables for Fast Routing Lookups. Sigcomm 1997.3-14.
[14] B. Lampson, V. Srinivasan, G. Varghese. IP lookups using multiway andmulticolumn search. Infocom 1998, 1248-1256.
[15] 许恪,许明伟,吴建平等.路由查找算法研究综述. 软件学报,2002,Vol.13(1):42-50.
[16] P. Gupta, S. Lin, N. McKeown. Routing lookups in hardware at memory access speeds. Infocom 1998, 1241-1248.
[17] S. Nilsson, G. Karlsson. Fast address lookup for Internet routers. IFIP Intl Conf on Broadband Communications, Stuttgart, Germany, April 1-3, 1998.
[18] P. Gupta, B. Prabhakar, S. Boyd. Near-optimal routing lookups with bounded worst case performance. Infocom, March 2000.1184-1192.
[19] Sklower, Keith. A tree-based routing table for Berkeley Unix,Technical Report, Berkeley: University of California, 1993.
[20] Ergun, F., Mittra, S., Sahinalp, S.C., et al. A dynamic lookup scheme for bursty access patterns. IEEE INFOCOM, 2001,1444~1453.
[21] 卢锡城,管剑波. 高速路由与交换技术现状及发展趋势. 国防科技大学学报,2005,Vol27(5):1-5.
[22] Narlikar, Girija, Zane, F. Performance modeling for fast IP lookups. Proceedings of the ACM SIGMETRICS, 2001, 1~12.
[23] Baboescu F,Singh S,Varghese G.Packet Classification for Core Routers:Is There an Alternative to CAMs.IEEE INFOCOM 2003,2003-2008.
[24] SinghS, Baboescu F,Varghese G,et al. Packet Classification Using Multidimensional Cutting.In proceedings of ACM SIGCOMM'03.http://www.acm.org/sigcomm/sigcomm2003/papers/p213-singh.pdf,2003-08-25.
[25] 王鼎兴,陈国良编著,互连网络结构分析,北京,科学出版社,1996.
[26] 毛用才,胡奇英编著,随机过程,西安,西安电子科技大学出版社,1998.
[27] N.Mckeown, M.Izzard, A.Mekkittikul, et al. The Tiny Tera: A Packet Switch Core. IEEE Micro Jan/Feb 1997, 26-33.
[28] J.Duato,S.Yalamanchili, L.Ni., Interconnection Networks, an Engineering Approach, Morgan-Kaufman Press, 2003.
[29] N.Mckeown,C.Calamvokis,S.-T.Chuang, A 2.5Tb/s LCS switch core. Hot Chip XIII,Aug,2001.
[30] W.Dally, B.Towles, Principles and practices of interconnection networks, Morgan-Kaufman Press, 2004.
[31] Dally .W. J. Scalable Switching Fabrics for Internet Routers[WhitePaper]. Avici Systems, Inc. 1997. http://www.avici.com/technology/whitepapers/.
[32] TeraPlex -Architecture Overview[WhiterPaper]. Pluris, Inc. 2001. http://www.pluris.com/technology/whitepapers/.
[33] 顾华玺,直连网络关键技术的研究,博士学位论文,西安电子科技大学,中国西安,2005.
[34] Dally.W. J. Performance Analysis of k-ary n-cube Interconnection Networks[J]. IEEE Transactions on Computers, 1990, C-39(6) : 775-785.
[35] Karol M, Hluchyj M, Morgan S. Input versus output queueing on a space division switch. IEEE Transactions on Communication, 1988,35(12):1347~1356.
[36] 杨君刚,大容量路由器交换网络拓扑结构研究.硕士学位论文,西安电子科技大学,中国西安,2003 年 3 月.
[37] Tamir Y, Frazier G. Dynamically-Allocated multi-queue buffer for VLSI communication switches. IEEE Transactions on Computers, 1992,41(6):725~737.
[38] H. Zhang. Service discipline for guaranteed performance service in packet-switching networks [ J ] . Proceeding of IEEE ,Oct . 1995 , 83 :1374 - 1399.
[39] R. Bennett ,H. Zhang. WF2Q:Worst-case fair weighted fair queueing[C] . IEEE INFOCOM ,1996 .120 - 128.
[40] J . C. R. Bennett , H. Zhang. Hierarchical packet fair queueing algorithms . IEEE/ ACM Trans. on Networking ,1997 ,Vol.5(5) :675 - 689.
[41] 杨帆,分组调度及接入允许控制算法的研究,博士学位论文,西安电子科技大学,中国西安,2002 年 6 月.
[42] P. Goyal ,H.M. Vin. Start - time fair queueing :A scheduling algorithm for integrated services packet switching networks. IEEE/ ACM Trans. on Networking ,1997 ,Vol.5(5) :690 - 703.
[43] J . A. Cobb et al . Time-shift scheduling : Fair scheduling of flow in high-speed networks . IEEE/ ACM Trans. on Networking , 1999 :274 - 285.
[44] 庞 斌, 贺思敏, 高 文. 高速 IP 路由器中输入排队调度算法综述. 软件学报,2003,Vol.14(5):1011-1022.
[45] LaMarie R.O, Serpanos D.N. Two dimensional round-robin schedulers for packet switches with multiple input-queues.IEEE/ACM Transactions on Networking. 1994,Vol.2(5):471-482.
[46] Hopcroft. J E, et al. An n2.5 algorithm for maximum matching in bipartite graphs. SIAM J Comput. 1973. 225- 231.
[47] McKeown N, Anderson TE. A quantitative comparison of scheduling algorithmsfor input-queued switches. Computer Networks and ISDN Systems, 1998,30(24):2309~2326.
[48] Chao H J. Saturn: A terabit packet switch using dual round robin. IEEE Communications Magazine, 2000,38(12):78~84.
[49] Marsan MA, Bianco A, Giaccone P, et al. Input-Queued router architectures exploiting cell-based switching fabrics. Computer Networks, 2001,37(5):541~559.
[50] M A Marsan, A.Bianco, E.Filippi, et al. A comparison of input queuing cell switch architectures. IEEE Workshop on Broadband Switching Systems(BSS '99). Kingston, Ontario, Canada, 1999.
[51] Serpanos DN, Antoniadis PI. FIRM: A class of distributed scheduling algorithms for high-speed ATM switches with multiple input queues. IEEE INFOCOM, 2000. 548~555
[52] 熊庆旭.输入排队结构交换机分组调度研究.通信学报,2005,VoL.26(6):118-129.
[53] Anderson T, Owicki S, Saxes J,et al. High speed switch scheduling for local area networks, IEEE/ACM Transactions on Computer Systems, 1993,11(4):319~352.
[54] Tassiulas T. Linear complexity algorithms for maximum throughput in radio networks and input queued switches. IEEE INFOCOM, 1998. 533~539.
[55] J.G.Dai and B.prabhakar. The throughput of data switches with and without speedup. INFOCOM 2000.556-564.
[56] Giaccone P, Prabhakar B, Shah D. Towards simple, high-performance schedulers for high-aggregate bandwidth switches. IEEE INFOCOM, 2002. 1160~1169.
[57] N. McKeown. iSLIP: a scheduling algorithm for input-queued switches. IEEE Transaction on Networking, 1999, Vol. 7(2): 188-201.
[58] N. McKeown . Scheduling algorithms for input-queued cell switches, PhD Thesis, University of California, Berkeley, May 1995.
[59] Chang CS, Chen WJ, Huang HY. Birkhoff-von Neumann input buffered crossbar switches. IEEE INFOCOM, 2000. 1614~1623
[60] E.Leonardi, M.Mellia, M.Ajmone Marsan, et al. Stability of maximal size matching scheduling in input-queued cell switches. International Conference on Communications (ICC), vol. 3, 2000. 1758-1763.
[61] Andrews M, Vojnovic M. Scheduling reserved traffic in input-queued switches: new delay bounds via probabilistic techniques. IEEE INFOCOM, 2003. 764-774.
[62] Clos. A study of nonblocking switching fabric networks. BSTJ, 1953,Vol.32(5):406~424
[63] Chao H. Jonathan, Jing Zhigang, Soung Y. L. Matching Algorithms for Three-Stage Bufferless Clos Network Switches. IEEE Communication Magazine 2003,Vol.41(10): 46~54.
[64] Chao H. J., Deng K-L,Z. Jing. A Petabit Photonic Packet Switch (P3S). IEEE INFOCOM , 2003.775-785.
[65] Andrzej Jajszczyk. Nonblocking, Repackable, and Rearrangeable Clos Networks: Fifty Years of the Theory Evolution. IEEE Communications Magazine, 2003 ,Vol.41(10):28-33.
[66] Chao H. J., Deng K-L., and Z. Jing. PetaStar: A Petabit Photonic Packet Switch. IEEE JSAC Special Issue on High-Performance Optical/Electronic Switches/Routers for High-Speed Internet, 2003, vol. 21(7):1096-1112.
[67] E. Oki, Z. Jing, R. Rojas-Cessa, and Chao H. J.. Concurrent Round-Robin-Based Dispatching Schemes for Clos-Network Switches. IEEE/ACM Trans. Networking. 2002,vol.10( 6):830-844.
[68] Stephens D., Zhang H.. Implementing Distributed Packet Fair Queueing in A Scalable Switch Architecture. IEEE INFOCOM, 1998, 282-290
[69] K. Yoshigoe ,K. Christensen. A Parallel-Polled Virtual Output Queued Switch with a Buffered Crossbar. proceedings of the 2001 IEEE Workshop on High Performance Switching and Routing,May 2001 . 271-275.
[70] K. Pun, M. Hamdi. Distro: A Distributed Static Round-Robin Scheduling Algorithm for Bufferless Clos-Network Switches. IEEE Globecom 2002, vol. 3, 2298-2302.
[71] S. Iyer, A. Awadallah, N. McKeown. Analysis of a packet switch with memories running slower than the line rate. IEEE INFOCOM, 2000, 529-537.
[72] Isaac Keslassy, Shang-Tse Chuang,Kyoungsik Yu, et al. Scaling Internet Routers Using Optics. Computer Communication Review, 2003,Vol. 33( 4): 189-200.
[73] MA. Marsan, A. Bianco, P. Giaccone, et al. Packet Scheduling in Input-Queued Cell-Based Switches. INFOCOM 2001 .1085-1094.
[74] Chang C.S., D.S. Lee Y.S. Jou. Load-balancedd Birkhoff-von Neumann switches, part I: one-stage buffering. Computer Communications, 2002,Vol.25(6):611-622.
[75] Chang CS, Lee DS, Lien CM. Load balanced Birkhoff-von Neumann switches Part II: Multi-Stage buffering. Computer Communications, 2002,Vol.25(6):623~634.
[76] Mark W. Goudreau, Stavros G. Kolliopoulosy, Satish B. Rao. Scheduling Algorithms for Input-Queued Switches:Randomized Techniques and Experimental Evaluation. INFOCOM ,2000, 1624-1643.
[77] Saad Mneimneh, Vishal Sharma,Kai-yeung Siu. Switching Using Parallel Input-Output Queued Switches with No Speedup.IEEE/ACM Transaction on Networking, 2002,vol.10(5):653~665.
[78] J. Turner ,N. Yamanaka. Architectural Choices in Large Scale ATM Switches. IEICE Trans. Commun. 1998,vol..E81-B( 2): 120-137.
[79] 陈震,可伸展多级分组交换网络结构的研究,博士学位论文,西安电子科技大学,中国西安,2004.
[80] Khotimsky D.A., Krishnan S.. Stability analysis of a parallel packet switch with bufferless input demultiplexors. International Conference on Communications (ICC2001). Helsinki, 2001,100-106.
[81] W. Wang, Libin Dong, Wayne Wolf. A distributed switch architecture with dynamic load-balancing and parallel input-queued crossbar for terabit switch fabrics. IEEE INFOCOM,2002, 352-361.
[82] E.Leonardi, M.Mellia, et al. Bounds on average delays and queue size averages and variances in input-queued cell-based switches. IEEE INFOCOM. 2001,1095-1103.
[83] Shah D, Kopikare M. Delay bounds for the approximate maximum weight matching algorithm for input queued switches. IEEE INFOCOM, 2002. 1024~1031.
[84] Shah D. Maximal matching scheduling is good enough. Globecom,2003, 3009-3013.
[85] Zhong Hakhan, Xu Du, Zhu Zhenyu. A parallel packet switch supporting variable-length packets. International Conference on Communications, Circuits and Systems Proceedings, 2005, 613-617.
[86] Ganjali Y, Keshavarzian A, Shah D. Input queued switches: Cell switching vs. packet switching. IEEE INFOCOM.2003. 1651-1658.
[87] Lei Shi, Wenjie Li, et al. Flow mapping in the load balancing parallel packet switches. Workshop on High Performance Switching and Routing. , 2005, 254-258.
[88] Javidi T, Magill R, Hrabik T. A high-throughput scheduling algorithm for a buffered crossbar switch fabric. Proceedings of the IEEE InternationalConference on Communications (ICC), 2001. 1586~1591.
[89] Prabhakar B, McKeown N, Ahuja R. Multicast scheduling for input-queued switches. IEEE Journal on Selected Areas in Communications, 1997,15(5):855~866.
[90] McKeown N, Mekkittikui A, Anantharam V, Walrand J. Achieving 100% throughput in an input-queued switch. IEEE Transactions on Communication, 1999,47(8):1260~1267
[91] Parekh AK, Gallager RG.. A generalized processor sharing approach to flow control in integrated service networks: the single-node case. IEEE/ACM Transactions on Networking, 1993,1(3):344~357.
[92] Isaac Keslassy, Cheng-Shang Chang, Nick McKeown, et al, Optimal Load-Balancing. IEEE INFOCOM 2005, March 2005.1712-1722
[93] Mihaela Enachescu, Yashar Ganjali, Ashish Goel,etl,Routers with very small buffers, IEEE INFOCOM'06, April 2006.1-11.
[94] Shang-Tse Chuang, Sundar Iyer, Nick McKeown. Practical Algorithms for Performance Guarantees in Buffered Crossbars , IEEE INFOCOM 2005, March 2005.981-991.
[95] Sundar Iyer ,Nick McKeown . Using Constraint Sets to Achieve Delay Bounds in CIOQ Switches . IEEE Communication Letters, 2003,Vol.7(6): 275-277,.
[96] Mekkittikui A, McKeown N. A starvation-free algorithm for achieving 100% throughput in input-queued switches. Proceedings of the IEEE International Conference on Computer Communications and Networks (ICCCN),1996. 226~231.
[97] Mekkittikui A, McKeown N. A practical scheduling algorithm to achieve 100% throughput in input-queued switches. IEEE INFOCOM. 1998. 792~799.
[98] Tabatabaee V, Tassiulas L. MNCM a new class of efficient scheduling algorithms for input-buffered switches with no speedup. IEEE INFOCOM’03. 2003. 1406-1413.
[99] Lotfi Mhamdi ,Mounir Hamdi .Practical Scheduling Algorithms for High-Performance Packet Switches,2003 IEEE International Conference on Communications, 2003.1659-1663.
[100] R. Rojas-Cessa, E. Oki,H. J. Chao. CIXOB-k: Combined Input-Crosspoint-Output Buffered Packet Switch, Proceedings of IEEE GLOBECOM,2001. 2654-2660.
[101] Magill R B ,Rohrs C E ,Stevenson R L.Output queued switch emulation by fabrics with limited memory. IEEE J Select Areas Commun ,2003,21(4):606-615.
[102] M. Nabeshima. Performance Evaluation of A Combined Input and Crosspoint Queued Switch, IEICE Trans. Commun, E83-B:3,2000: 737-741.
[103] Yoshigoe K, Christensen K J. An evolution to crossbar switches with virtual output queuing and buffered cross points. IEEE Networks, 2003, 17(5): 48-56.
[104] [美]Mischa.S., 宽带网络性能分析,北京,清华大学出版社,1998.
[105] 张先迪,李正良主编,图论及其应用,北京,高等教育出版社,2005.
[106] Tarjan RE. Data structures and network algorithms. SIAM, 1983.
[107] Prabhakar P, Mckeown N. On the speedup required for combined input and output queued switching. Automatica, 1999,Vol. 35 (12):1909-1920.
[108] Chuang ST, Goel A, McKeown N. Matching output queueing with a combined input/output-queued switch. IEEE Journal on Selected Areas in Communications, 1999,17(6):1030~1039.
[109] Stoica I, Zhang H. Exact emulation of an output queueing switch by a combined input and output queueing switch. IEEE IWQoS, 1998. 218~224.
[110] Minkenber G C. Work-conservingness of CIOQ packet switches with limited output buffers. IEEE Comm Letter, 2002, 6(10):452-454.
[111] Krishna P, Patel NS, Charny A, S, et al. On the speedup required for work-conserving crossbar switches. IEEE Journal on Selected Areas in Communications, 1999,17(6):1057~1066.
[112] Gusfield D, Irving R. The Stable Marriage Problem: Structure and Algorithms. The MIT Press, 1989.
[113] Xiao Zhang ,Laxmi N. Bhuyan. An Efficient Scheduling Algorithm for Combined Input-Crosspoint-Queued (CICQ) Switches. Globecom, 2004.1168-1173.
[114] N. Chrysos, M. Katevenis. Weighted Fairness in Buffered Crossbar Scheduling. Proc. IEEE Workshop High Perf. Switching & Routing (HPSR 2003). 2003. 17-22.
[115] Cessa R R, et al. CIXB-1: combined input-one-cell-crosspoint buffered switch. IEEE HPSR, 2001.324-329.
[116] 田畅,分组并行交换体系结构研究,博士学位论文, 解放军理工大学,中国南京,2001.
[117] 刘亚社,中大规模 ATM 交换网络的研究,博士学位论文,西安电子科技大学,中国西安,1997.
[118] Rai I , Alanyali M. Uniform weighted round robin scheduling algorithms for input queued switches. IEEE ICC,2001, 2028-2032.
[119] Kam A C, Kai-Yeung shi. Linear-complexity algorithms for QoS support in input-queued switches with no speedup. IEEE JSAC, 1999,17(6):1040-1056.
[120] Zhang X, Bhuyan L N . Deficit round-robin scheduling for input-queued switches. IEEE JSAC, 2003, 21(4): 584-594.
[121] Bianco A, Franceschinis M, Chisolfi S. Frame-based matching algorithms for input-queued switches. IEEE HPSR’02, 2002. 69-76.
[122] Li S, Ansari N. Input-queued switching with QoS guarantees. IEEE INFOCOM , 1999. 1152-1159.
[123] Chao H. J., S. Y. Liew, Z. Jing. A Dual-Level Matching Algorithm for 3-stage Clos-Network Packet Switches. Proc. Hot Interconnects 11, Aug. 2003.38-43.
[124] Yang Y. Wang J.. Wide-sense Nonblocking Clos Networks Under Packing Strategy. IEEE Transactions on Computers, 1999,Vol. 48( 3): 265-284.
[125] V. E. Benes. Algebratic and Topological Properties of Connecting Networks. Bell System Tech. J., 1962,Vol.41,1201-1247.
[126] V. E. Benes.On Rearrangeable Three Stage Connecting Networks. Bell System Tech. J., 1962,Vol.41,1481-1492.
[127] E. Oki, R. Rojas-Cessa, Chao H. Jonathan. PCRRD: A Pipeline-Based Concurrent Round-Robin Dispatching Scheme for Clos-Network Switches. IEEE ICC 2002. 2121 -2125.
[128] P. Konghong, M. Hamdi.Static Round-robin Dispatching Schemes for Clos-network Switches. IEEE HPSR 2002. 329-333.
[129] Roberto.R.C, Eiji Oki, Chao H. Jonathan. Maximum Weight Matching Dispatching Scheme in Buffered Clos-Network Packet Switches. IEEE International Conference on Communications, 2004.1075-1079.
[130] M. Karol ,C-L. I. Performance Analysis of a Growable Architecture for Broadband Packet (ATM) Switching. GLOBECOM ’89, 1989. 1173–80.
[131] Y. Li, S. S. Panwar, Chao H. J. The Dual Round Robin Matching Switch with Exhaustive Service. Proc High-Perf. Switching and Routing, 2002.58-63.
[132] Oki Eiji, Roberto Rojas-Cessa, chao H.J.. A pinpline-based approach for maximal-sized matching scheduling in input-buffered switches.IEEE Communication Letters,2001,5(6):263~265.
[133] M.P. Haynos ,Y. Yang. An analytical model on the blocking probability of a fault-tolerant network. IEEE Trans. Parallel and Distributed Systems, 1999,10(10):1040-1051.
[134] Yang Y.Y., Wang J.. A fault-tolerant rearrangeable permutation network. IEEE Transaction on Computers, 2004, 53(4):414-426.
[135] S. Iyer ,Nick McKeown. Making Parallel Packet Switches Practical. IEEE INFOCOM, 2001,1680-1687.
[136] Keslassy I, McKeown N. Maintaining packet order in two-stage switches. IEEE INFOCOM, 2002. 1032~1041.
[137] S Y Liew, G Hu, H J Chao. Scheduling Algorithm for Shared Fiber-Delay-Line Optical Packet Switches Part I : The Single-stage Case. IEEE Journal of Lightwave Technology, 2005, 23(4):1586-1600.
[138] S Jiang, G Hu, S Y Liew, H J Chao. Scheduling Algorithm for Shared Fiber-Delay-Line Optical Packet Switches PartII: The 3-Stage Clos-Network Case. IEEE Journal of Lightwave Technology, 2005, 23(4):1601-1608.
[139] L Dittmann, C Develder, et al. The European IST Project DAVID:A Viable Approach Toward Optical Packet Switching. IEEE Journal on Selected Areas in Communications , 2003,21(7):1026~1040
[2] 中 国 互 联 网 络 发 展 状 况 统 计 报 ,http://www.cnnic.cn/uploadfiles/doc /2007/7/18/ .doc
[3] What will high perfermence switches and routers look like in ten years.http://www.tlc-networks.polito.it/hpsr 2003.
[4] A. M. Odlyzko.Internet traffic growth: Sources and implications. Optical Transmission Systems and Equipment for WDM Networking II, B. B. Dingel, W. Weiershausen, A. K. Dutta, and K.-I. Sato, eds., Proc. SPIE, vol. 5247, 2003, pp. 1-15. availabile http://www.dtc.umn.edu/~odlyzko/doc/networks.html.
[5] A. M. Odlyzko .Comments on the Larry Roberts and Caspian Networks study of Internet traffic growth. The Cook Report on the Internet, Dec. 2001, pp. 12-15.
[6] K. G. Coffman, A. M. Odlyzko. Growth of the Internet. In Optical Fiber Telecommunications IV B: Systems and Impairments, I. P. Kaminow and T. Li, eds. Academic Press, 2002, pp. 17-56.
[7] K. Fukuchi. 10.92Tbit/s(273x40 Gbit/s) triple-band/ultra-dense WDM optical repeated transmission experiment. in Proc. OFC2001, PD24, 2001
[8] S. Bigo, Y. Frignac, G. Charlet, et al. 10.2 Tbit/s (256x42.7 Gbit/s PDM/WDM) transmission over 100 km Teralight TM fiber with 1.28 bit/s Hz spectral efficiency. OFC’2001 Technical Digest, Anaheim, California USA, PD25.
[9] Fabio M.Chiussi, Andrea Francini. Scalable Electronic Packet Switches.IEEE Journal on Selected Areas in Communication, 2003,Vol.21(4):486-500.
[10] 刘增基,鲍民权,邱智亮,交换原理与技术,人民邮电出版社,2007 年 9月.
[11] 3G 及 下 一 代 网 络 建 设 : 带 动 高 端 路 由 器 市 场 发 展 的 火 车 头http://www.ccwresearch.com.cn/store/article_content.asp?articleId=4461.
[12] Fuller,V., Li, T., et al. Classless Inter-domain Routing (CIDR): an Address Assignment and Aggregation Strategy. RFC1519,1993
[13] A. Brodnik, S. Carlsson, M. Degermark,et al.Small Forwarding Tables for Fast Routing Lookups. Sigcomm 1997.3-14.
[14] B. Lampson, V. Srinivasan, G. Varghese. IP lookups using multiway andmulticolumn search. Infocom 1998, 1248-1256.
[15] 许恪,许明伟,吴建平等.路由查找算法研究综述. 软件学报,2002,Vol.13(1):42-50.
[16] P. Gupta, S. Lin, N. McKeown. Routing lookups in hardware at memory access speeds. Infocom 1998, 1241-1248.
[17] S. Nilsson, G. Karlsson. Fast address lookup for Internet routers. IFIP Intl Conf on Broadband Communications, Stuttgart, Germany, April 1-3, 1998.
[18] P. Gupta, B. Prabhakar, S. Boyd. Near-optimal routing lookups with bounded worst case performance. Infocom, March 2000.1184-1192.
[19] Sklower, Keith. A tree-based routing table for Berkeley Unix,Technical Report, Berkeley: University of California, 1993.
[20] Ergun, F., Mittra, S., Sahinalp, S.C., et al. A dynamic lookup scheme for bursty access patterns. IEEE INFOCOM, 2001,1444~1453.
[21] 卢锡城,管剑波. 高速路由与交换技术现状及发展趋势. 国防科技大学学报,2005,Vol27(5):1-5.
[22] Narlikar, Girija, Zane, F. Performance modeling for fast IP lookups. Proceedings of the ACM SIGMETRICS, 2001, 1~12.
[23] Baboescu F,Singh S,Varghese G.Packet Classification for Core Routers:Is There an Alternative to CAMs.IEEE INFOCOM 2003,2003-2008.
[24] SinghS, Baboescu F,Varghese G,et al. Packet Classification Using Multidimensional Cutting.In proceedings of ACM SIGCOMM'03.http://www.acm.org/sigcomm/sigcomm2003/papers/p213-singh.pdf,2003-08-25.
[25] 王鼎兴,陈国良编著,互连网络结构分析,北京,科学出版社,1996.
[26] 毛用才,胡奇英编著,随机过程,西安,西安电子科技大学出版社,1998.
[27] N.Mckeown, M.Izzard, A.Mekkittikul, et al. The Tiny Tera: A Packet Switch Core. IEEE Micro Jan/Feb 1997, 26-33.
[28] J.Duato,S.Yalamanchili, L.Ni., Interconnection Networks, an Engineering Approach, Morgan-Kaufman Press, 2003.
[29] N.Mckeown,C.Calamvokis,S.-T.Chuang, A 2.5Tb/s LCS switch core. Hot Chip XIII,Aug,2001.
[30] W.Dally, B.Towles, Principles and practices of interconnection networks, Morgan-Kaufman Press, 2004.
[31] Dally .W. J. Scalable Switching Fabrics for Internet Routers[WhitePaper]. Avici Systems, Inc. 1997. http://www.avici.com/technology/whitepapers/.
[32] TeraPlex -Architecture Overview[WhiterPaper]. Pluris, Inc. 2001. http://www.pluris.com/technology/whitepapers/.
[33] 顾华玺,直连网络关键技术的研究,博士学位论文,西安电子科技大学,中国西安,2005.
[34] Dally.W. J. Performance Analysis of k-ary n-cube Interconnection Networks[J]. IEEE Transactions on Computers, 1990, C-39(6) : 775-785.
[35] Karol M, Hluchyj M, Morgan S. Input versus output queueing on a space division switch. IEEE Transactions on Communication, 1988,35(12):1347~1356.
[36] 杨君刚,大容量路由器交换网络拓扑结构研究.硕士学位论文,西安电子科技大学,中国西安,2003 年 3 月.
[37] Tamir Y, Frazier G. Dynamically-Allocated multi-queue buffer for VLSI communication switches. IEEE Transactions on Computers, 1992,41(6):725~737.
[38] H. Zhang. Service discipline for guaranteed performance service in packet-switching networks [ J ] . Proceeding of IEEE ,Oct . 1995 , 83 :1374 - 1399.
[39] R. Bennett ,H. Zhang. WF2Q:Worst-case fair weighted fair queueing[C] . IEEE INFOCOM ,1996 .120 - 128.
[40] J . C. R. Bennett , H. Zhang. Hierarchical packet fair queueing algorithms . IEEE/ ACM Trans. on Networking ,1997 ,Vol.5(5) :675 - 689.
[41] 杨帆,分组调度及接入允许控制算法的研究,博士学位论文,西安电子科技大学,中国西安,2002 年 6 月.
[42] P. Goyal ,H.M. Vin. Start - time fair queueing :A scheduling algorithm for integrated services packet switching networks. IEEE/ ACM Trans. on Networking ,1997 ,Vol.5(5) :690 - 703.
[43] J . A. Cobb et al . Time-shift scheduling : Fair scheduling of flow in high-speed networks . IEEE/ ACM Trans. on Networking , 1999 :274 - 285.
[44] 庞 斌, 贺思敏, 高 文. 高速 IP 路由器中输入排队调度算法综述. 软件学报,2003,Vol.14(5):1011-1022.
[45] LaMarie R.O, Serpanos D.N. Two dimensional round-robin schedulers for packet switches with multiple input-queues.IEEE/ACM Transactions on Networking. 1994,Vol.2(5):471-482.
[46] Hopcroft. J E, et al. An n2.5 algorithm for maximum matching in bipartite graphs. SIAM J Comput. 1973. 225- 231.
[47] McKeown N, Anderson TE. A quantitative comparison of scheduling algorithmsfor input-queued switches. Computer Networks and ISDN Systems, 1998,30(24):2309~2326.
[48] Chao H J. Saturn: A terabit packet switch using dual round robin. IEEE Communications Magazine, 2000,38(12):78~84.
[49] Marsan MA, Bianco A, Giaccone P, et al. Input-Queued router architectures exploiting cell-based switching fabrics. Computer Networks, 2001,37(5):541~559.
[50] M A Marsan, A.Bianco, E.Filippi, et al. A comparison of input queuing cell switch architectures. IEEE Workshop on Broadband Switching Systems(BSS '99). Kingston, Ontario, Canada, 1999.
[51] Serpanos DN, Antoniadis PI. FIRM: A class of distributed scheduling algorithms for high-speed ATM switches with multiple input queues. IEEE INFOCOM, 2000. 548~555
[52] 熊庆旭.输入排队结构交换机分组调度研究.通信学报,2005,VoL.26(6):118-129.
[53] Anderson T, Owicki S, Saxes J,et al. High speed switch scheduling for local area networks, IEEE/ACM Transactions on Computer Systems, 1993,11(4):319~352.
[54] Tassiulas T. Linear complexity algorithms for maximum throughput in radio networks and input queued switches. IEEE INFOCOM, 1998. 533~539.
[55] J.G.Dai and B.prabhakar. The throughput of data switches with and without speedup. INFOCOM 2000.556-564.
[56] Giaccone P, Prabhakar B, Shah D. Towards simple, high-performance schedulers for high-aggregate bandwidth switches. IEEE INFOCOM, 2002. 1160~1169.
[57] N. McKeown. iSLIP: a scheduling algorithm for input-queued switches. IEEE Transaction on Networking, 1999, Vol. 7(2): 188-201.
[58] N. McKeown . Scheduling algorithms for input-queued cell switches, PhD Thesis, University of California, Berkeley, May 1995.
[59] Chang CS, Chen WJ, Huang HY. Birkhoff-von Neumann input buffered crossbar switches. IEEE INFOCOM, 2000. 1614~1623
[60] E.Leonardi, M.Mellia, M.Ajmone Marsan, et al. Stability of maximal size matching scheduling in input-queued cell switches. International Conference on Communications (ICC), vol. 3, 2000. 1758-1763.
[61] Andrews M, Vojnovic M. Scheduling reserved traffic in input-queued switches: new delay bounds via probabilistic techniques. IEEE INFOCOM, 2003. 764-774.
[62] Clos. A study of nonblocking switching fabric networks. BSTJ, 1953,Vol.32(5):406~424
[63] Chao H. Jonathan, Jing Zhigang, Soung Y. L. Matching Algorithms for Three-Stage Bufferless Clos Network Switches. IEEE Communication Magazine 2003,Vol.41(10): 46~54.
[64] Chao H. J., Deng K-L,Z. Jing. A Petabit Photonic Packet Switch (P3S). IEEE INFOCOM , 2003.775-785.
[65] Andrzej Jajszczyk. Nonblocking, Repackable, and Rearrangeable Clos Networks: Fifty Years of the Theory Evolution. IEEE Communications Magazine, 2003 ,Vol.41(10):28-33.
[66] Chao H. J., Deng K-L., and Z. Jing. PetaStar: A Petabit Photonic Packet Switch. IEEE JSAC Special Issue on High-Performance Optical/Electronic Switches/Routers for High-Speed Internet, 2003, vol. 21(7):1096-1112.
[67] E. Oki, Z. Jing, R. Rojas-Cessa, and Chao H. J.. Concurrent Round-Robin-Based Dispatching Schemes for Clos-Network Switches. IEEE/ACM Trans. Networking. 2002,vol.10( 6):830-844.
[68] Stephens D., Zhang H.. Implementing Distributed Packet Fair Queueing in A Scalable Switch Architecture. IEEE INFOCOM, 1998, 282-290
[69] K. Yoshigoe ,K. Christensen. A Parallel-Polled Virtual Output Queued Switch with a Buffered Crossbar. proceedings of the 2001 IEEE Workshop on High Performance Switching and Routing,May 2001 . 271-275.
[70] K. Pun, M. Hamdi. Distro: A Distributed Static Round-Robin Scheduling Algorithm for Bufferless Clos-Network Switches. IEEE Globecom 2002, vol. 3, 2298-2302.
[71] S. Iyer, A. Awadallah, N. McKeown. Analysis of a packet switch with memories running slower than the line rate. IEEE INFOCOM, 2000, 529-537.
[72] Isaac Keslassy, Shang-Tse Chuang,Kyoungsik Yu, et al. Scaling Internet Routers Using Optics. Computer Communication Review, 2003,Vol. 33( 4): 189-200.
[73] MA. Marsan, A. Bianco, P. Giaccone, et al. Packet Scheduling in Input-Queued Cell-Based Switches. INFOCOM 2001 .1085-1094.
[74] Chang C.S., D.S. Lee Y.S. Jou. Load-balancedd Birkhoff-von Neumann switches, part I: one-stage buffering. Computer Communications, 2002,Vol.25(6):611-622.
[75] Chang CS, Lee DS, Lien CM. Load balanced Birkhoff-von Neumann switches Part II: Multi-Stage buffering. Computer Communications, 2002,Vol.25(6):623~634.
[76] Mark W. Goudreau, Stavros G. Kolliopoulosy, Satish B. Rao. Scheduling Algorithms for Input-Queued Switches:Randomized Techniques and Experimental Evaluation. INFOCOM ,2000, 1624-1643.
[77] Saad Mneimneh, Vishal Sharma,Kai-yeung Siu. Switching Using Parallel Input-Output Queued Switches with No Speedup.IEEE/ACM Transaction on Networking, 2002,vol.10(5):653~665.
[78] J. Turner ,N. Yamanaka. Architectural Choices in Large Scale ATM Switches. IEICE Trans. Commun. 1998,vol..E81-B( 2): 120-137.
[79] 陈震,可伸展多级分组交换网络结构的研究,博士学位论文,西安电子科技大学,中国西安,2004.
[80] Khotimsky D.A., Krishnan S.. Stability analysis of a parallel packet switch with bufferless input demultiplexors. International Conference on Communications (ICC2001). Helsinki, 2001,100-106.
[81] W. Wang, Libin Dong, Wayne Wolf. A distributed switch architecture with dynamic load-balancing and parallel input-queued crossbar for terabit switch fabrics. IEEE INFOCOM,2002, 352-361.
[82] E.Leonardi, M.Mellia, et al. Bounds on average delays and queue size averages and variances in input-queued cell-based switches. IEEE INFOCOM. 2001,1095-1103.
[83] Shah D, Kopikare M. Delay bounds for the approximate maximum weight matching algorithm for input queued switches. IEEE INFOCOM, 2002. 1024~1031.
[84] Shah D. Maximal matching scheduling is good enough. Globecom,2003, 3009-3013.
[85] Zhong Hakhan, Xu Du, Zhu Zhenyu. A parallel packet switch supporting variable-length packets. International Conference on Communications, Circuits and Systems Proceedings, 2005, 613-617.
[86] Ganjali Y, Keshavarzian A, Shah D. Input queued switches: Cell switching vs. packet switching. IEEE INFOCOM.2003. 1651-1658.
[87] Lei Shi, Wenjie Li, et al. Flow mapping in the load balancing parallel packet switches. Workshop on High Performance Switching and Routing. , 2005, 254-258.
[88] Javidi T, Magill R, Hrabik T. A high-throughput scheduling algorithm for a buffered crossbar switch fabric. Proceedings of the IEEE InternationalConference on Communications (ICC), 2001. 1586~1591.
[89] Prabhakar B, McKeown N, Ahuja R. Multicast scheduling for input-queued switches. IEEE Journal on Selected Areas in Communications, 1997,15(5):855~866.
[90] McKeown N, Mekkittikui A, Anantharam V, Walrand J. Achieving 100% throughput in an input-queued switch. IEEE Transactions on Communication, 1999,47(8):1260~1267
[91] Parekh AK, Gallager RG.. A generalized processor sharing approach to flow control in integrated service networks: the single-node case. IEEE/ACM Transactions on Networking, 1993,1(3):344~357.
[92] Isaac Keslassy, Cheng-Shang Chang, Nick McKeown, et al, Optimal Load-Balancing. IEEE INFOCOM 2005, March 2005.1712-1722
[93] Mihaela Enachescu, Yashar Ganjali, Ashish Goel,etl,Routers with very small buffers, IEEE INFOCOM'06, April 2006.1-11.
[94] Shang-Tse Chuang, Sundar Iyer, Nick McKeown. Practical Algorithms for Performance Guarantees in Buffered Crossbars , IEEE INFOCOM 2005, March 2005.981-991.
[95] Sundar Iyer ,Nick McKeown . Using Constraint Sets to Achieve Delay Bounds in CIOQ Switches . IEEE Communication Letters, 2003,Vol.7(6): 275-277,.
[96] Mekkittikui A, McKeown N. A starvation-free algorithm for achieving 100% throughput in input-queued switches. Proceedings of the IEEE International Conference on Computer Communications and Networks (ICCCN),1996. 226~231.
[97] Mekkittikui A, McKeown N. A practical scheduling algorithm to achieve 100% throughput in input-queued switches. IEEE INFOCOM. 1998. 792~799.
[98] Tabatabaee V, Tassiulas L. MNCM a new class of efficient scheduling algorithms for input-buffered switches with no speedup. IEEE INFOCOM’03. 2003. 1406-1413.
[99] Lotfi Mhamdi ,Mounir Hamdi .Practical Scheduling Algorithms for High-Performance Packet Switches,2003 IEEE International Conference on Communications, 2003.1659-1663.
[100] R. Rojas-Cessa, E. Oki,H. J. Chao. CIXOB-k: Combined Input-Crosspoint-Output Buffered Packet Switch, Proceedings of IEEE GLOBECOM,2001. 2654-2660.
[101] Magill R B ,Rohrs C E ,Stevenson R L.Output queued switch emulation by fabrics with limited memory. IEEE J Select Areas Commun ,2003,21(4):606-615.
[102] M. Nabeshima. Performance Evaluation of A Combined Input and Crosspoint Queued Switch, IEICE Trans. Commun, E83-B:3,2000: 737-741.
[103] Yoshigoe K, Christensen K J. An evolution to crossbar switches with virtual output queuing and buffered cross points. IEEE Networks, 2003, 17(5): 48-56.
[104] [美]Mischa.S., 宽带网络性能分析,北京,清华大学出版社,1998.
[105] 张先迪,李正良主编,图论及其应用,北京,高等教育出版社,2005.
[106] Tarjan RE. Data structures and network algorithms. SIAM, 1983.
[107] Prabhakar P, Mckeown N. On the speedup required for combined input and output queued switching. Automatica, 1999,Vol. 35 (12):1909-1920.
[108] Chuang ST, Goel A, McKeown N. Matching output queueing with a combined input/output-queued switch. IEEE Journal on Selected Areas in Communications, 1999,17(6):1030~1039.
[109] Stoica I, Zhang H. Exact emulation of an output queueing switch by a combined input and output queueing switch. IEEE IWQoS, 1998. 218~224.
[110] Minkenber G C. Work-conservingness of CIOQ packet switches with limited output buffers. IEEE Comm Letter, 2002, 6(10):452-454.
[111] Krishna P, Patel NS, Charny A, S, et al. On the speedup required for work-conserving crossbar switches. IEEE Journal on Selected Areas in Communications, 1999,17(6):1057~1066.
[112] Gusfield D, Irving R. The Stable Marriage Problem: Structure and Algorithms. The MIT Press, 1989.
[113] Xiao Zhang ,Laxmi N. Bhuyan. An Efficient Scheduling Algorithm for Combined Input-Crosspoint-Queued (CICQ) Switches. Globecom, 2004.1168-1173.
[114] N. Chrysos, M. Katevenis. Weighted Fairness in Buffered Crossbar Scheduling. Proc. IEEE Workshop High Perf. Switching & Routing (HPSR 2003). 2003. 17-22.
[115] Cessa R R, et al. CIXB-1: combined input-one-cell-crosspoint buffered switch. IEEE HPSR, 2001.324-329.
[116] 田畅,分组并行交换体系结构研究,博士学位论文, 解放军理工大学,中国南京,2001.
[117] 刘亚社,中大规模 ATM 交换网络的研究,博士学位论文,西安电子科技大学,中国西安,1997.
[118] Rai I , Alanyali M. Uniform weighted round robin scheduling algorithms for input queued switches. IEEE ICC,2001, 2028-2032.
[119] Kam A C, Kai-Yeung shi. Linear-complexity algorithms for QoS support in input-queued switches with no speedup. IEEE JSAC, 1999,17(6):1040-1056.
[120] Zhang X, Bhuyan L N . Deficit round-robin scheduling for input-queued switches. IEEE JSAC, 2003, 21(4): 584-594.
[121] Bianco A, Franceschinis M, Chisolfi S. Frame-based matching algorithms for input-queued switches. IEEE HPSR’02, 2002. 69-76.
[122] Li S, Ansari N. Input-queued switching with QoS guarantees. IEEE INFOCOM , 1999. 1152-1159.
[123] Chao H. J., S. Y. Liew, Z. Jing. A Dual-Level Matching Algorithm for 3-stage Clos-Network Packet Switches. Proc. Hot Interconnects 11, Aug. 2003.38-43.
[124] Yang Y. Wang J.. Wide-sense Nonblocking Clos Networks Under Packing Strategy. IEEE Transactions on Computers, 1999,Vol. 48( 3): 265-284.
[125] V. E. Benes. Algebratic and Topological Properties of Connecting Networks. Bell System Tech. J., 1962,Vol.41,1201-1247.
[126] V. E. Benes.On Rearrangeable Three Stage Connecting Networks. Bell System Tech. J., 1962,Vol.41,1481-1492.
[127] E. Oki, R. Rojas-Cessa, Chao H. Jonathan. PCRRD: A Pipeline-Based Concurrent Round-Robin Dispatching Scheme for Clos-Network Switches. IEEE ICC 2002. 2121 -2125.
[128] P. Konghong, M. Hamdi.Static Round-robin Dispatching Schemes for Clos-network Switches. IEEE HPSR 2002. 329-333.
[129] Roberto.R.C, Eiji Oki, Chao H. Jonathan. Maximum Weight Matching Dispatching Scheme in Buffered Clos-Network Packet Switches. IEEE International Conference on Communications, 2004.1075-1079.
[130] M. Karol ,C-L. I. Performance Analysis of a Growable Architecture for Broadband Packet (ATM) Switching. GLOBECOM ’89, 1989. 1173–80.
[131] Y. Li, S. S. Panwar, Chao H. J. The Dual Round Robin Matching Switch with Exhaustive Service. Proc High-Perf. Switching and Routing, 2002.58-63.
[132] Oki Eiji, Roberto Rojas-Cessa, chao H.J.. A pinpline-based approach for maximal-sized matching scheduling in input-buffered switches.IEEE Communication Letters,2001,5(6):263~265.
[133] M.P. Haynos ,Y. Yang. An analytical model on the blocking probability of a fault-tolerant network. IEEE Trans. Parallel and Distributed Systems, 1999,10(10):1040-1051.
[134] Yang Y.Y., Wang J.. A fault-tolerant rearrangeable permutation network. IEEE Transaction on Computers, 2004, 53(4):414-426.
[135] S. Iyer ,Nick McKeown. Making Parallel Packet Switches Practical. IEEE INFOCOM, 2001,1680-1687.
[136] Keslassy I, McKeown N. Maintaining packet order in two-stage switches. IEEE INFOCOM, 2002. 1032~1041.
[137] S Y Liew, G Hu, H J Chao. Scheduling Algorithm for Shared Fiber-Delay-Line Optical Packet Switches Part I : The Single-stage Case. IEEE Journal of Lightwave Technology, 2005, 23(4):1586-1600.
[138] S Jiang, G Hu, S Y Liew, H J Chao. Scheduling Algorithm for Shared Fiber-Delay-Line Optical Packet Switches PartII: The 3-Stage Clos-Network Case. IEEE Journal of Lightwave Technology, 2005, 23(4):1601-1608.
[139] L Dittmann, C Develder, et al. The European IST Project DAVID:A Viable Approach Toward Optical Packet Switching. IEEE Journal on Selected Areas in Communications , 2003,21(7):1026~1040