可扩展路由器交换网络容错性能优化研究
|
摘要
可扩展路由器是未来互联网的核心设备，交换网络是可扩展路由器的关键部件。容错功能是可扩展路由器交换网络最重要的功能之一，但容错功能会增加系统开销并降低系统性能，因此在保持容错功能的基础上优化可扩展路由器交换网络容错性能的研究具有重要理论意义和实用价值。
本文对于可扩展路由器交换网络容错性能优化的研究包括三个方面：拓扑健壮性、故障检测方法和交换节点资源分配策略。其中，拓扑健壮性是容错的基础，故障检测是发现故障的主要手段，交换节点资源分配策略是优化带故障的可扩展路由器交换网络性能的有效方法。容错性能优化是利用冗余资源对带故障的交换网络进行性能优化。
论文的主要工作和创新点如下：
（1）综述了可扩展路由器交换网络容错相关研究的现状，分析了可扩展路由器交换网络容错性能优化仍需解决的问题。
（2）提出了可扩展路由器交换网络的健壮性评价方法，结合可扩展路由器交换网络随机故障模型验证了该方法较现有方法更适于可扩展路由器交换网络的健壮性评价。
（3）提出了一种针对可扩展路由器交换网络的高效率故障检测方法，设计了局部定向故障检测器，可以解决可扩展路由器交换网络的合意问题。通过建模分析和仿真实验验证，局部定向故障检测器在故障发现速度和产生负载方面均优于现有故障检测器。
（4）提出了一种基于包调度算法的交换节点资源分配策略，优化了可扩展路由器交换网络交换节点的容错性能。理论分析和仿真实验证明，交换节点资源分配策略能以较低的实现代价达到了近似最优的带宽资源分配效果。
（5）设计了一个支持容错性能优化的可扩展路由器交换网络节点原型设计方案，验证了提出的故障检测方法和交换节点资源分配策略方面研究成果的正确性。该方案具有支持容错性能优化、支持高速转发和支持大规模扩展等优点。
Scalable switch networks are key components of scalable routers whichplay very important role in the next generation Internet. Although faulttolerance is essential for scalable switch networks, it increases the redundancyand reduces system performance. Hence performance optimization for faulttolerance is a significant issue for the research and implementation of scalableswitch networks.
In this thesis，we research on the key techniques of fault tolerant scalableswitch fabric，and our main goal is to optimize the performance of scalableswitch fabrics with failed components. This thesis is referred to three kinds ofoptimization techniques: topology robustness analysis, failure detection anddiagnose, resource allocation policy on switch nodes.
The main contributions and conclusions are as follows:
(1) A thorough survey is conducted on the research of performanceoptimization for fault tolerance on scalable switch network and its relatedresearch fields. It also introduces three critical aspects for performanceoptimization for fault tolerance on scalable switch networks.
(2) A novel robustness measure named Failure Influence is proposed.Existing robustness measures are not suitable for scalable switch fabric underrandom fault model. It has been proved that Failure Influence is an effectivemeasure towards scalable switch fabric topology and it can distinguishrobustness difference among similar topologie.
(3) Partial directional failure detector which based on partial directionalgossip algorithm is proposed. The consensus problem of partial directionalfailure detector is proved and an efficiency model is also introduced. Partialdirectional failure detector is outperforming existing hierarchal failuredetectors in both efficiency and message load.
(4) Packet scheduler based resource allocation policy is proposed forswitch nodes, Extend hardware optimized bit reversal permutation is proposedand it has been proved to be an efficient resource allocation policy for scalableswitch fabrics. Hardware optimized bit reversal permutation can archive high scheduling performance with low implementation complexity.
(5) A fault tolerant switch node prototype is introduced, which usespartial directional failure detector and hardware optimized bit reversalpermutation scheduler as its key parts. This prototype has larger capacities,lower implementation complexity and simpler expansion.
本文对于可扩展路由器交换网络容错性能优化的研究包括三个方面：拓扑健壮性、故障检测方法和交换节点资源分配策略。其中，拓扑健壮性是容错的基础，故障检测是发现故障的主要手段，交换节点资源分配策略是优化带故障的可扩展路由器交换网络性能的有效方法。容错性能优化是利用冗余资源对带故障的交换网络进行性能优化。
论文的主要工作和创新点如下：
（1）综述了可扩展路由器交换网络容错相关研究的现状，分析了可扩展路由器交换网络容错性能优化仍需解决的问题。
（2）提出了可扩展路由器交换网络的健壮性评价方法，结合可扩展路由器交换网络随机故障模型验证了该方法较现有方法更适于可扩展路由器交换网络的健壮性评价。
（3）提出了一种针对可扩展路由器交换网络的高效率故障检测方法，设计了局部定向故障检测器，可以解决可扩展路由器交换网络的合意问题。通过建模分析和仿真实验验证，局部定向故障检测器在故障发现速度和产生负载方面均优于现有故障检测器。
（4）提出了一种基于包调度算法的交换节点资源分配策略，优化了可扩展路由器交换网络交换节点的容错性能。理论分析和仿真实验证明，交换节点资源分配策略能以较低的实现代价达到了近似最优的带宽资源分配效果。
（5）设计了一个支持容错性能优化的可扩展路由器交换网络节点原型设计方案，验证了提出的故障检测方法和交换节点资源分配策略方面研究成果的正确性。该方案具有支持容错性能优化、支持高速转发和支持大规模扩展等优点。
Scalable switch networks are key components of scalable routers whichplay very important role in the next generation Internet. Although faulttolerance is essential for scalable switch networks, it increases the redundancyand reduces system performance. Hence performance optimization for faulttolerance is a significant issue for the research and implementation of scalableswitch networks.
In this thesis，we research on the key techniques of fault tolerant scalableswitch fabric，and our main goal is to optimize the performance of scalableswitch fabrics with failed components. This thesis is referred to three kinds ofoptimization techniques: topology robustness analysis, failure detection anddiagnose, resource allocation policy on switch nodes.
The main contributions and conclusions are as follows:
(1) A thorough survey is conducted on the research of performanceoptimization for fault tolerance on scalable switch network and its relatedresearch fields. It also introduces three critical aspects for performanceoptimization for fault tolerance on scalable switch networks.
(2) A novel robustness measure named Failure Influence is proposed.Existing robustness measures are not suitable for scalable switch fabric underrandom fault model. It has been proved that Failure Influence is an effectivemeasure towards scalable switch fabric topology and it can distinguishrobustness difference among similar topologie.
(3) Partial directional failure detector which based on partial directionalgossip algorithm is proposed. The consensus problem of partial directionalfailure detector is proved and an efficiency model is also introduced. Partialdirectional failure detector is outperforming existing hierarchal failuredetectors in both efficiency and message load.
(4) Packet scheduler based resource allocation policy is proposed forswitch nodes, Extend hardware optimized bit reversal permutation is proposedand it has been proved to be an efficient resource allocation policy for scalableswitch fabrics. Hardware optimized bit reversal permutation can archive high scheduling performance with low implementation complexity.
(5) A fault tolerant switch node prototype is introduced, which usespartial directional failure detector and hardware optimized bit reversalpermutation scheduler as its key parts. This prototype has larger capacities,lower implementation complexity and simpler expansion.
引文
[1]第27次中国互联网络发展状况统计报告[EB/OL].[2011-02-15].http://www.cnnic.cn/research/bgxz/tjbg/201101/P020110221534255749405.pdf.
[2] Odlyzko M. Internet traffic growth: sources and implications. Proceedings of SPIEOptical Transmission Systems and Equipment for WDM Networking. Orlando, FL,USA: SPIE,2003:1-15.
[3] Keslassy I, Chuang S, Yu K, et al. Scaling Internet Routers Using Optics.Proceedings of the Special Interest Group on Data Communication. Karlsruhe,Germany: ACM Press,2003:189-200.
[4] Iyer S, Nick M. Analysis of the Parallel Packet Switch Architecture. IEEE/ACMTransactions on Networking,2003,11(2):314-324.
[5] T640Routing Node and TX Matrix Platform: Architecture. White Paper
[EB/OL].[2011-01-10]. http://www.juniper.net.
[6] Cisco CRS-1Series Carrier Routing System Getting Started Guide [EB/OL].
[2011-01-10]. http://www.cisco.com.
[7] The Avici TSR: Cornerstone of the Multi-Terabit Core [EB/OL].[2011-01-10].http://www.avici.com.
[8] Kohler E. The Click modular router [D]. Massachusetts: Department of ElectricalEngineering and Computer Science, MIT University,2001.
[9] Handley M, Hodson O, Kohler E. Xorp: An open platform for network research.ACM SIGCOMM Computer Communication Review,2003,33(1):53-57.
[10] Karlin S, Peterson L. VERA: An Extensible Router Architecture. In: Proceedingsof the4th International Conference on Open Architectures and NetworkProgramming, USA: Elsevier,2001:3-14.
[11] Welling G, Ott M, Mathur S. CLARA: A cluster-based active router architecture.IEEE Micro,2001,21(1):16-25.
[12] Jiani Guo, Fang Chen, L. Bhuyan, et al. A cluster-based active router architecturesupporting video/audio stream trans-coding service. Proceedings of InternationalParallel and Distributed Processing Symposium, Washington, USA: ACM Press,2003:8-15.
[13]管剑波.集群路由器体系结构及其关键技术的研究[博士学位论文].长沙:国防科技大学,2008.
[14] Zhao Youjian, Yue Zuhui, Wu Jianping. Research on Next-Generation ScalableRouters Implemented with H-Torus Topology. Journal of Computer Science andTechnology.2008,23(4):684-693.
[15] Ott M, Welling G, Mathur S, el al. The JOURNEY active network model. IEEEJournal on Selected Areas in Communications.2001,19(3):527-537.
[16]张小平,刘振华,赵有健,等.可扩展路由器.软件学报.2008,19(6):1452-1464.
[17]关洪涛.可扩展路由器交换结构性能优化研究[博士学位论文].北京:清华大学计算机系,2010.
[18] Dally W. Scalable Switching Fabrics for Internet Routers [EB/OL].[2011-1-20]http://www.avici.com/technology/whitepapers/TSRfab
[19] Dally W, Towles B. Principles and practices of interconnection networks. SanFrancisco, CA, USA: Morgan Kaufmann,2004.
[20] Brandes U and Erlebach T. Network analysis. Berlin, Germany: Springer-Verlag,2005.
[21] Koren I, Krishna C. Fault-Tolerant systems. San Francisco, CA, USA: MorganKaufmann,2007.
[22] Ebeling C. An Introduction to Reliability and Maintainability Engineering. NewYork city, NY, United States: McGraw-Hill,1997.
[23] Blough D, Sullivan G. Voting Using Predispositions. IEEE Transactions onReliability.1994,43:604-616.
[24] Wallace D, Coleman C. Application and Improvement of Software ReliabilityModels. Report of Task323-08: NASA Software Assurance Technology Center,2001.
[25] McEliece R. The Theory of Information and Coding.2nd edition, London, UK:Cambridge University Press,2002.
[26] Luk F, Park H. An Analysis of Algorithm-Based Fault Tolerance Techniques.Journal of Parallel and Distributed Computing.1988,5:172-184.
[27] Krishna C, Shin K, Lee Y. Optimization Criteria for Checkpointing.Communications of the ACM.1984,27:1008-1012.
[28] Tantawi A, Ruschitzka M. Performance Analysis of Checkpointing Strategies.ACM Transactions on Computing Systems.1984,2:123–144.
[29] Elnozahy E, Alvisi L, Wang Y, et al. A Survey of Rollback-Recovery Protocols inMessage-Passing Systems. ACM Computing Surveys.2002,34:375-408.
[30] Rao T, Fujiwara E. Error-Control Coding for Computer Systems. Prentice Hall,1989.
[31] Rangarajan S, Setia S, Tripathi S. A Fault Tolerant Algorithm for Replicated DataManagement. IEEE Transactions on Parallel and Distributed Systems.1995,6:1271–1282.
[32]富弘毅,杨学军.大规模并行计算机系统硬件故障容错技术综述.计算机工程与科学.2010, vol32(10), pp:38-43.
[33] Oh N, Shirvani P, McCluskey, et al. Error detection by duplicated instructions insuper-scalar processors. IEEE Transactions on Reliability,2002,51(1):63-75.
[34] Oh N, Mitra S, and McCluskey E. ED4I: error detection by diverse data andduplicated instructions. IEEE Transactions on Computers,2002,51(2):180-187.
[35] Duato J, Yalamanchili S and Ni L. Interconnection Network: an engineeringapproach. San Francisco, CA, United States: Morgan Kaufmann,2003.
[36] Agarwal A. Limits on interconnection network performance. IEEE Transactions onParallel and Distributed Systems,1991,2(4):398-412.
[37] Jajszczyk A. Nonblocking, repackable, and rearrangeable Clos networks: fiftyyears of the theory evolution. IEEE Communications Magazine,2003,41(10):28-33.
[38] Benes V. Optimal Rearrangeable Multistage Connecting Networks. Bell SystemsTechnical Journal,1964,43(7):1641–1656.
[39] Chuanlin Wu, Feng T. On a class of multistage interconnection networks. IEEETrans. Computer,1980,29(8):694–702.
[40] Clos C. A Study of Non-blocking Switching Networks. The Bell System TechnicalJournal,1953,32(2):406-424.
[41] Dally W. Performance analysis of k-ary n-cube interconnection networks. IEEETransactions on Computers,1990,39(6):775-785.
[42] Yue Zuhui, Zhao Youjian, Wu Jianping, et al. Designing Scalable Routers with aNew Switching Architecture. Proceedings of the Autonomic and AutonomousSystems and International Conference on Networking and Services.2005:1-12.
[43] Dally W. Performance analysis of k-ary n-cube interconnection networks. IEEETransactions on Computers.1990,39(6):775-785.
[44] LaForge L, Korver K, Fadali M. What designers of Bus and network architectursshould konw about hypercubes. IEEE Transactions on Computers.2003,52(4):525-544.
[45] Lakshmivarahan, Ring S. Torus and hypercube architectures algorithms forparallel computing. Parallel Computing.1999,25:1877-1906.
[46] Wang Dajin. A low-cost fault-tolerant structure for the hypercube. Journal ofSupercomputing.2001,20(3):203-216.
[47] Su C, Shin K. Adaptive Fault-Tolerant deadlock-free routing in meshes andhypercube. IEEE Transactions on Computers.1996,45(6):666-683.
[48] Liu Zhenhua, Zhang Xiaoping, Zhao Youjian, et al. An Asymptotically MinimalNode-Degree Topology for Load-Balanced Architectures. Proceedings of GlobalTelecommunications Conference.2008:1-6.
[49]张小平.可扩展路由器体系结构关键技术研究[博士学位论文].北京:清华大学计算机系,2008.
[50] Krishnamoorthy V, Thulasiraman K, Swamy M. Incremental distance and diametersequences of a graph: new measures of network performance. Transactions onComputers.1990,39:230–237.
[51] Boesch F, Harary F, Kabell J. Graphs as models of communication networkvulnerability: Connectivity and persistence. Networks,1981,11:57–63.
[52] Boesch F, Thomas R. On graphs of invulnerable communication nets. IEEETransactions on Circuits Theory.1970,17:183-192.
[53] Chvatal V. Tough graphs and Hamiltonian circuits. Discrete Mathematics.2006,306:910-917.
[54] Tainiter M. A new deterministic network reliablity measure. Networks.1976,6(3):191-204.
[55] Palmer C, Siganos G, Faloutsos M, et al. The connectivity and fault-tolerance ofthe Internet topology. Workshop on Network-Related Data Management,2001:203-216.
[56] Boorstyn R, Frank H. Large-scale network topological optimizationCommunications. IEEE Transactions on legacy.1977,25:29-47.
[57] Konstantinidou S, Snyder L. Chaos router: Architecture and performance.Proceedings of the18th International Symposium on Computer Architecture.1991:79-88.
[58] Dally W, Seitz C. Deadlock-free message routing in multiprocessorinterconnection networks. IEEE Transactions on Computers.1987,5:547-553.
[59] Gaughan P, Yalamanchili S. A family of fault-tolerant routing protocols for directmultiprocessor networks. IEEE Transactions on Parallel and Distributed Systems.1995,6(5):482-497.
[60] Duato J. Scouting: Fully adaptive, deadlock-free routing in faulty pipelinednetworks. Proceedings of the International Conference on Parallel and DistributedSystems.1994:608-613.
[61] Glass C, Ni L. Fault-tolerant wormhole routing inmeshes. Proceedings of the23rdInternational Symposium on Fault-Tolerant Computing.1993:240-249.
[62] Dally W, Aoki H. Deadlock-free adaptive routing in multicomputer networks usingvirtual channels. Trans. on Parallel and Distributed Systems.1993,4(4):466-475.
[63] Duato J. A theory to increase the effective redundancy in wormhole networks.Parallel Processing Letters.1994,4(1):125-138.
[64] Duato J. A theory of fault-tolerant routing in wormhole networks. Proceedings ofthe International Conference on Parallel and Distributed Systems.1994:600–607.
[65] Chen MingSyan, Shin Kang. Adaptive fault-tolerant routing in hypercubemulticomputers. IEEE Transactions on Computers, vol. C-39, no.12, pp.1406–1416, December1990.
[66] Lee T, Hayes J. A fault-tolerant communication scheme for hypercube computers.IEEE Transactions on Computers.1992, C-41(10):1242–1256.
[67] Chien Ai, Kim J. Planar-adaptive routing: Low-cost adaptive networks formultiprocessors. Proceedings of the19th International Symposium on ComputerArchitecture.1992,268-277.
[68] Chalasani S, Boppana R. Fault-tolerant wormhole routing in tori. Proceedings ofthe8th International Conference on Supercomputing,1994:146–155.
[69] Xiang Dong, Chen Ai, Wu Jie. Reliable Broadcasting in Wormhole-RoutedHypercube-Connected Networks Using Local Safety Information. Transactions onReliability.2003,52(2):245-256.
[70] Chiu Geming, Wu Shuipao. A fault-tolerant routing strategy in hypercube systems.IEEE Transactions on Computers.1996,45:143-155.
[71] Wu Jie. Adaptive fault-tolerant routing in cube-based multicomputers using safetyvectors. IEEE Trans. Parallel Distributed System.1998,9(4):321-334.
[72] Al-Sadi J, Day K, Ould-Khaoua M. Unsafety vectors: a new fault-tolerant routingfor the binary n-cube. Journal of Systems Architecture.2002,47(9):783-793.
[73] Parekh A, Gallager R. A generalized processor sharing approach to flow control inintegrated services networks: the single node case. IEEE/ACMTransactions onNetworking.1993,1(2):344-357.
[74] Parekh A, Gallager R. A generalized processor sharing approach to flow control inintegrated services networks: the single node case. IEEE/ACMTransactions onNetworking.1993,1(2):344-357.
[75] Bennett J, Zhang H. WF2Q: worst-case fair weighted fair queueing. Proceedings ofIEEE INFOCOM. San Francisco, California:1996,1:120-128.
[76] Guo C. SRR: an o (1) time-complexity packet scheduler for flows in multiservicepacket networks. IEEE/ACM Transactions on Networking.2004,12(6):1144-1155.
[77] Cheung S, Pencea C. BSFQ: bin sort fair queueing. Proceedings of Twenty-FirstAnnual Joint Conference of the IEEE Computer and Communications Societies.2002,3:1640-1649.
[78] Caprita B, Chan W, Nieh J, et al. Group ratio round-robin: O(1) proportional sharescheduling for uniprocessor and multiprocessor systems. Proceedings of the annualconference on USENIX Annual Technical Conference. Anaheim, CA: USENIXAssociation,2005:36-36.
[79] Yuan Xin, Duan Zhenhai. FRR: a proportional and worst-case fair round robinscheduler. Proceedings of24th Annual Joint Conference of the IEEE Computerand Communications Societies.2005,2:831-842.
[80] Tse E. Switch fabric design for high performance IP routers: A survey. Journal ofSystems Architecture.2004,51:571-601.
[81] Krishnamoorthy V, Thulasiraman K, and Swamy M. Incremental Distance andDiameter Sequences of a Graph: New Measures of Network Performance. IEEETransaction on Computer.1990,39:230-237.
[82] Gartner F. Fundamentals of fault-tolerant distributed computing in asynchronousenvironments. ACM Computer Survey.1999,31:1-26.
[83]张祖平.规则网络容错路由算法及可靠组播的研究[博士学位论文].长沙:中南大学计算机系,2005.
[84] Cheng Xian, Ibe O. Reliability of a Class of Multistage Interconnection Networks.IEEE Transaction on Parallel Distribute System.1992,3:241-246.
[85] Albert R, Jeong H, Barabasi A. Error and attack tolerance of complex networks.Nature.2000,406:378-384.
[86] Najjar W and Gaudiot J. Network Resilience: A Measure of Network FaultTolerance. IEEE Transaction on Computer.1990,39:174-181.
[87] Tangmunarunkit H, Govindan R, Jamin S, et al. Network topologies, power laws,and hierarchy. ACM SIGCOMM Computer Communication Review,2002,32:76-86.
[88] Boesch F, Thomas R. On graphs of invulnerable communication nets. IEEETransactions on Circuits Theory.1970,17:183-192.
[89] Fischer M, Lynch N, Paterson M. Impossibility of distributed consensus with onefaulty process.Journal of the ACM.1985,32(2):374-382.
[90] Chandra T, Toueg S. Unreliable failure detectors for reliable distributed systems.Journal of ACM,1996,43(2):225-267.
[91] Gupta I, Chandra T, Goldszmidt G. On scalable and efficient distributed failuredetectors. Proceedings of the twentieth annual ACM symposium on Principles ofdistributed computing. NY, USA: ACM,2001:170-179.
[92] Renesse R, Minsky Y, Hayden M. A gossip-style failure detection service.Proceedings of the IFIP International Conference on Distributed Systems Platformsand Open Distributed Processing. London, UK: Springer-Verlag,2009:55-70.
[93] Renesse R, Birman K, Glade B, et al. Horus: a Flexible Group CommunicationsSystem. Ithaca, NY, USA: Cornell University,1995.
[94] Eugster P, Guerraoui R, Handurukande S, et al. Lightweight probabilistic broadcast.ACM Transaction on Computer Systems,2003,21(4):341-374.
[95] Delaet S, Ducourthial B, Tixeuil S. Tolerating transient and intermittent failures.Journal of Parallel Distribute computer.2002,62(5):961-981.
[96] Kermarrec A, Massoulie L, Ganesh A. Probabilistic Reliable Dissemination inLarge-Scale Systems. Transaction on Parallel Distribute System,2003,14(3):248-258.
[97] Joffroy B, Sylvie D, Shlomi D, and et al. Transient fault detectors. DistributedComputing,2007,20(1):39-51.
[98] Dwork C, Lynch N, Stockmeyer L.1988. Consensus in the presence of partialsynchrony. Journal of the ACM,1988,35(2):288-323.
[99] Aguilera M, Chen Wei, Toueg S. Heartbeat: a Timeout-Free Failure Detector forQuiescent Reliable Communication. Ithaca, NY, USA: Cornell University,1997.
[100] Barborak M, Dahbura A, Malek M. The Consensus problem in Fault-TolerantComputing. ACM Computing Surveys,1993,25(2):171-220.
[101] DOLEV D, DWORK C, ANCISTOCKMEYER L. On the minimal synchronismneeded for distributed consensus. Journal of ACM.1987,34(1):77-97.
[102] Dwork C, Lynch N, Stockmeyer L. Consensus in the presence of partial synchrony.Journal of the ACM.1988,35(2):288-323.
[103] Fetzer C, Cristian F. On the possibility of consensus in asynchronous systems.Proceeding of the1995Pacific Rim Int’l Symp. On Fault-Tolerance Systems.Newport Beach, CA,1995:271-280.
[104] Cristian F, Fetzer C. The Timed Asynchronous System Model. Technical ReportCSE97-519, Department of Computer Science，UCSD,1997.
[105] Ben M. Another advantage of free-choice: Completely asynchronous agreementprotocols. Proceedings of the2nd annual ACM symposium on Principles ofDistributed Computing.1983:27-30.
[106] Castro M, Liskov B. Practical Byzantine fault tolerance. Proceedings of3rd Symp.Operating Systems Design and Implementation,1999:173-186.
[107] Bracha G. An asynchronous [(n-1)/3]-resilient consensus protocol. Proceedings of3rd ACM Symp. On principles of Distributed Computing.1984:154-162.
[108] Zhang L. A new architecture for packet switching network protocols [D]. Dept.Elect. Eng. and Comput Sci., MIT,1989.
[109] Valente P. Exact GPS simulation and optimal fair scheduling with logarithmiccomplexity. IEEE/ACM Transactions on Networking.2007,15(6):1454–1466.
[110] Golestani S. A self-clocked fair queueing scheme for broadband applications.Proceedings of13th Proceedings Networking for Global Communications.1994,2:636-646.
[111] Goyal P, Vin H, Cheng H. Start-time fair queueing: a scheduling algorithm forintegrated services packet switching networks. IEEE/ACM Transactions onNetworking.1997,5(5):690-704.
[112] Stiliadis D, Varma A. Efficient fair queueing algorithms for packetswitchednetworks. IEEE/ACM Transactions on Networking.1998,6(2):175-185.
[113] Cobb J, Gouda M, El-Nahas A. Time-shift scheduling-fair scheduling of flows inhigh-speed networks. Transactions on Networking.1998,6(3):274-285.
[114] Xu J, Lipton R. On fundamental tradeoffs between delay bounds andcomputational complexity in packet scheduling algorithms. Networking,IEEE/ACM Transactions on Networking.2005,13(1):15-28.
[115] Shreedhar M, Varghese G. Efficient fair queuing using deficit round-robin.IEEE/ACM Transactions on Networking.1996,4(3):375-385.
[116] Lenzini L, Mingozzi E, and Stea G. Aliquem: a novel DRR implementation toachieve better latency and fairness at o(1) complexity. Proceedings of Tenth IEEEInternational Workshop on Quality of Service.2002:77-86.
[117] Saha D, Mukherjee S, Tripathi S. Carry-over round robin: a simple cell schedulingmechanism for ATM networks. IEEE/ACM Transactions on Networking.1998,6(6):779-796.
[118] Garg R, Chen X. RRR: recursive round robin scheduler. Proceedings of GlobalTelecommunications Conference. The Bridge to Global Integration.1998,1:422-432.
[119] Ramabhadran S, Pasquale J. The stratified round robin scheduler: Design, analysisand implementation. IEEE/ACM Transactions on Networking.2006,14(6):1362-1373.
[120] Dally W. Virtual-channel flow control. IEEE Transactions on Parallel andDistributed Systems.1992,3(2):194-205.
[121] Rexford J, Shin K. Support for multiple classes of traffic in multicomputer routers.Proceedings of the Workshop on Parallel Computer Routing and Communication.1994:116-130.
[122] Chaskar H, Madhow U. Fair Scheduling With Tunable Latency: A Round-RobinApproach. IEEE/ACM Transaction on networking.2003:11(4).
[123] Blake T, Trivedi S. Multistage interconnection network reliability. IEEETransactions on Computers.1989,38(11):1600-1604.
[2] Odlyzko M. Internet traffic growth: sources and implications. Proceedings of SPIEOptical Transmission Systems and Equipment for WDM Networking. Orlando, FL,USA: SPIE,2003:1-15.
[3] Keslassy I, Chuang S, Yu K, et al. Scaling Internet Routers Using Optics.Proceedings of the Special Interest Group on Data Communication. Karlsruhe,Germany: ACM Press,2003:189-200.
[4] Iyer S, Nick M. Analysis of the Parallel Packet Switch Architecture. IEEE/ACMTransactions on Networking,2003,11(2):314-324.
[5] T640Routing Node and TX Matrix Platform: Architecture. White Paper
[EB/OL].[2011-01-10]. http://www.juniper.net.
[6] Cisco CRS-1Series Carrier Routing System Getting Started Guide [EB/OL].
[2011-01-10]. http://www.cisco.com.
[7] The Avici TSR: Cornerstone of the Multi-Terabit Core [EB/OL].[2011-01-10].http://www.avici.com.
[8] Kohler E. The Click modular router [D]. Massachusetts: Department of ElectricalEngineering and Computer Science, MIT University,2001.
[9] Handley M, Hodson O, Kohler E. Xorp: An open platform for network research.ACM SIGCOMM Computer Communication Review,2003,33(1):53-57.
[10] Karlin S, Peterson L. VERA: An Extensible Router Architecture. In: Proceedingsof the4th International Conference on Open Architectures and NetworkProgramming, USA: Elsevier,2001:3-14.
[11] Welling G, Ott M, Mathur S. CLARA: A cluster-based active router architecture.IEEE Micro,2001,21(1):16-25.
[12] Jiani Guo, Fang Chen, L. Bhuyan, et al. A cluster-based active router architecturesupporting video/audio stream trans-coding service. Proceedings of InternationalParallel and Distributed Processing Symposium, Washington, USA: ACM Press,2003:8-15.
[13]管剑波.集群路由器体系结构及其关键技术的研究[博士学位论文].长沙:国防科技大学,2008.
[14] Zhao Youjian, Yue Zuhui, Wu Jianping. Research on Next-Generation ScalableRouters Implemented with H-Torus Topology. Journal of Computer Science andTechnology.2008,23(4):684-693.
[15] Ott M, Welling G, Mathur S, el al. The JOURNEY active network model. IEEEJournal on Selected Areas in Communications.2001,19(3):527-537.
[16]张小平,刘振华,赵有健,等.可扩展路由器.软件学报.2008,19(6):1452-1464.
[17]关洪涛.可扩展路由器交换结构性能优化研究[博士学位论文].北京:清华大学计算机系,2010.
[18] Dally W. Scalable Switching Fabrics for Internet Routers [EB/OL].[2011-1-20]http://www.avici.com/technology/whitepapers/TSRfab
[19] Dally W, Towles B. Principles and practices of interconnection networks. SanFrancisco, CA, USA: Morgan Kaufmann,2004.
[20] Brandes U and Erlebach T. Network analysis. Berlin, Germany: Springer-Verlag,2005.
[21] Koren I, Krishna C. Fault-Tolerant systems. San Francisco, CA, USA: MorganKaufmann,2007.
[22] Ebeling C. An Introduction to Reliability and Maintainability Engineering. NewYork city, NY, United States: McGraw-Hill,1997.
[23] Blough D, Sullivan G. Voting Using Predispositions. IEEE Transactions onReliability.1994,43:604-616.
[24] Wallace D, Coleman C. Application and Improvement of Software ReliabilityModels. Report of Task323-08: NASA Software Assurance Technology Center,2001.
[25] McEliece R. The Theory of Information and Coding.2nd edition, London, UK:Cambridge University Press,2002.
[26] Luk F, Park H. An Analysis of Algorithm-Based Fault Tolerance Techniques.Journal of Parallel and Distributed Computing.1988,5:172-184.
[27] Krishna C, Shin K, Lee Y. Optimization Criteria for Checkpointing.Communications of the ACM.1984,27:1008-1012.
[28] Tantawi A, Ruschitzka M. Performance Analysis of Checkpointing Strategies.ACM Transactions on Computing Systems.1984,2:123–144.
[29] Elnozahy E, Alvisi L, Wang Y, et al. A Survey of Rollback-Recovery Protocols inMessage-Passing Systems. ACM Computing Surveys.2002,34:375-408.
[30] Rao T, Fujiwara E. Error-Control Coding for Computer Systems. Prentice Hall,1989.
[31] Rangarajan S, Setia S, Tripathi S. A Fault Tolerant Algorithm for Replicated DataManagement. IEEE Transactions on Parallel and Distributed Systems.1995,6:1271–1282.
[32]富弘毅,杨学军.大规模并行计算机系统硬件故障容错技术综述.计算机工程与科学.2010, vol32(10), pp:38-43.
[33] Oh N, Shirvani P, McCluskey, et al. Error detection by duplicated instructions insuper-scalar processors. IEEE Transactions on Reliability,2002,51(1):63-75.
[34] Oh N, Mitra S, and McCluskey E. ED4I: error detection by diverse data andduplicated instructions. IEEE Transactions on Computers,2002,51(2):180-187.
[35] Duato J, Yalamanchili S and Ni L. Interconnection Network: an engineeringapproach. San Francisco, CA, United States: Morgan Kaufmann,2003.
[36] Agarwal A. Limits on interconnection network performance. IEEE Transactions onParallel and Distributed Systems,1991,2(4):398-412.
[37] Jajszczyk A. Nonblocking, repackable, and rearrangeable Clos networks: fiftyyears of the theory evolution. IEEE Communications Magazine,2003,41(10):28-33.
[38] Benes V. Optimal Rearrangeable Multistage Connecting Networks. Bell SystemsTechnical Journal,1964,43(7):1641–1656.
[39] Chuanlin Wu, Feng T. On a class of multistage interconnection networks. IEEETrans. Computer,1980,29(8):694–702.
[40] Clos C. A Study of Non-blocking Switching Networks. The Bell System TechnicalJournal,1953,32(2):406-424.
[41] Dally W. Performance analysis of k-ary n-cube interconnection networks. IEEETransactions on Computers,1990,39(6):775-785.
[42] Yue Zuhui, Zhao Youjian, Wu Jianping, et al. Designing Scalable Routers with aNew Switching Architecture. Proceedings of the Autonomic and AutonomousSystems and International Conference on Networking and Services.2005:1-12.
[43] Dally W. Performance analysis of k-ary n-cube interconnection networks. IEEETransactions on Computers.1990,39(6):775-785.
[44] LaForge L, Korver K, Fadali M. What designers of Bus and network architectursshould konw about hypercubes. IEEE Transactions on Computers.2003,52(4):525-544.
[45] Lakshmivarahan, Ring S. Torus and hypercube architectures algorithms forparallel computing. Parallel Computing.1999,25:1877-1906.
[46] Wang Dajin. A low-cost fault-tolerant structure for the hypercube. Journal ofSupercomputing.2001,20(3):203-216.
[47] Su C, Shin K. Adaptive Fault-Tolerant deadlock-free routing in meshes andhypercube. IEEE Transactions on Computers.1996,45(6):666-683.
[48] Liu Zhenhua, Zhang Xiaoping, Zhao Youjian, et al. An Asymptotically MinimalNode-Degree Topology for Load-Balanced Architectures. Proceedings of GlobalTelecommunications Conference.2008:1-6.
[49]张小平.可扩展路由器体系结构关键技术研究[博士学位论文].北京:清华大学计算机系,2008.
[50] Krishnamoorthy V, Thulasiraman K, Swamy M. Incremental distance and diametersequences of a graph: new measures of network performance. Transactions onComputers.1990,39:230–237.
[51] Boesch F, Harary F, Kabell J. Graphs as models of communication networkvulnerability: Connectivity and persistence. Networks,1981,11:57–63.
[52] Boesch F, Thomas R. On graphs of invulnerable communication nets. IEEETransactions on Circuits Theory.1970,17:183-192.
[53] Chvatal V. Tough graphs and Hamiltonian circuits. Discrete Mathematics.2006,306:910-917.
[54] Tainiter M. A new deterministic network reliablity measure. Networks.1976,6(3):191-204.
[55] Palmer C, Siganos G, Faloutsos M, et al. The connectivity and fault-tolerance ofthe Internet topology. Workshop on Network-Related Data Management,2001:203-216.
[56] Boorstyn R, Frank H. Large-scale network topological optimizationCommunications. IEEE Transactions on legacy.1977,25:29-47.
[57] Konstantinidou S, Snyder L. Chaos router: Architecture and performance.Proceedings of the18th International Symposium on Computer Architecture.1991:79-88.
[58] Dally W, Seitz C. Deadlock-free message routing in multiprocessorinterconnection networks. IEEE Transactions on Computers.1987,5:547-553.
[59] Gaughan P, Yalamanchili S. A family of fault-tolerant routing protocols for directmultiprocessor networks. IEEE Transactions on Parallel and Distributed Systems.1995,6(5):482-497.
[60] Duato J. Scouting: Fully adaptive, deadlock-free routing in faulty pipelinednetworks. Proceedings of the International Conference on Parallel and DistributedSystems.1994:608-613.
[61] Glass C, Ni L. Fault-tolerant wormhole routing inmeshes. Proceedings of the23rdInternational Symposium on Fault-Tolerant Computing.1993:240-249.
[62] Dally W, Aoki H. Deadlock-free adaptive routing in multicomputer networks usingvirtual channels. Trans. on Parallel and Distributed Systems.1993,4(4):466-475.
[63] Duato J. A theory to increase the effective redundancy in wormhole networks.Parallel Processing Letters.1994,4(1):125-138.
[64] Duato J. A theory of fault-tolerant routing in wormhole networks. Proceedings ofthe International Conference on Parallel and Distributed Systems.1994:600–607.
[65] Chen MingSyan, Shin Kang. Adaptive fault-tolerant routing in hypercubemulticomputers. IEEE Transactions on Computers, vol. C-39, no.12, pp.1406–1416, December1990.
[66] Lee T, Hayes J. A fault-tolerant communication scheme for hypercube computers.IEEE Transactions on Computers.1992, C-41(10):1242–1256.
[67] Chien Ai, Kim J. Planar-adaptive routing: Low-cost adaptive networks formultiprocessors. Proceedings of the19th International Symposium on ComputerArchitecture.1992,268-277.
[68] Chalasani S, Boppana R. Fault-tolerant wormhole routing in tori. Proceedings ofthe8th International Conference on Supercomputing,1994:146–155.
[69] Xiang Dong, Chen Ai, Wu Jie. Reliable Broadcasting in Wormhole-RoutedHypercube-Connected Networks Using Local Safety Information. Transactions onReliability.2003,52(2):245-256.
[70] Chiu Geming, Wu Shuipao. A fault-tolerant routing strategy in hypercube systems.IEEE Transactions on Computers.1996,45:143-155.
[71] Wu Jie. Adaptive fault-tolerant routing in cube-based multicomputers using safetyvectors. IEEE Trans. Parallel Distributed System.1998,9(4):321-334.
[72] Al-Sadi J, Day K, Ould-Khaoua M. Unsafety vectors: a new fault-tolerant routingfor the binary n-cube. Journal of Systems Architecture.2002,47(9):783-793.
[73] Parekh A, Gallager R. A generalized processor sharing approach to flow control inintegrated services networks: the single node case. IEEE/ACMTransactions onNetworking.1993,1(2):344-357.
[74] Parekh A, Gallager R. A generalized processor sharing approach to flow control inintegrated services networks: the single node case. IEEE/ACMTransactions onNetworking.1993,1(2):344-357.
[75] Bennett J, Zhang H. WF2Q: worst-case fair weighted fair queueing. Proceedings ofIEEE INFOCOM. San Francisco, California:1996,1:120-128.
[76] Guo C. SRR: an o (1) time-complexity packet scheduler for flows in multiservicepacket networks. IEEE/ACM Transactions on Networking.2004,12(6):1144-1155.
[77] Cheung S, Pencea C. BSFQ: bin sort fair queueing. Proceedings of Twenty-FirstAnnual Joint Conference of the IEEE Computer and Communications Societies.2002,3:1640-1649.
[78] Caprita B, Chan W, Nieh J, et al. Group ratio round-robin: O(1) proportional sharescheduling for uniprocessor and multiprocessor systems. Proceedings of the annualconference on USENIX Annual Technical Conference. Anaheim, CA: USENIXAssociation,2005:36-36.
[79] Yuan Xin, Duan Zhenhai. FRR: a proportional and worst-case fair round robinscheduler. Proceedings of24th Annual Joint Conference of the IEEE Computerand Communications Societies.2005,2:831-842.
[80] Tse E. Switch fabric design for high performance IP routers: A survey. Journal ofSystems Architecture.2004,51:571-601.
[81] Krishnamoorthy V, Thulasiraman K, and Swamy M. Incremental Distance andDiameter Sequences of a Graph: New Measures of Network Performance. IEEETransaction on Computer.1990,39:230-237.
[82] Gartner F. Fundamentals of fault-tolerant distributed computing in asynchronousenvironments. ACM Computer Survey.1999,31:1-26.
[83]张祖平.规则网络容错路由算法及可靠组播的研究[博士学位论文].长沙:中南大学计算机系,2005.
[84] Cheng Xian, Ibe O. Reliability of a Class of Multistage Interconnection Networks.IEEE Transaction on Parallel Distribute System.1992,3:241-246.
[85] Albert R, Jeong H, Barabasi A. Error and attack tolerance of complex networks.Nature.2000,406:378-384.
[86] Najjar W and Gaudiot J. Network Resilience: A Measure of Network FaultTolerance. IEEE Transaction on Computer.1990,39:174-181.
[87] Tangmunarunkit H, Govindan R, Jamin S, et al. Network topologies, power laws,and hierarchy. ACM SIGCOMM Computer Communication Review,2002,32:76-86.
[88] Boesch F, Thomas R. On graphs of invulnerable communication nets. IEEETransactions on Circuits Theory.1970,17:183-192.
[89] Fischer M, Lynch N, Paterson M. Impossibility of distributed consensus with onefaulty process.Journal of the ACM.1985,32(2):374-382.
[90] Chandra T, Toueg S. Unreliable failure detectors for reliable distributed systems.Journal of ACM,1996,43(2):225-267.
[91] Gupta I, Chandra T, Goldszmidt G. On scalable and efficient distributed failuredetectors. Proceedings of the twentieth annual ACM symposium on Principles ofdistributed computing. NY, USA: ACM,2001:170-179.
[92] Renesse R, Minsky Y, Hayden M. A gossip-style failure detection service.Proceedings of the IFIP International Conference on Distributed Systems Platformsand Open Distributed Processing. London, UK: Springer-Verlag,2009:55-70.
[93] Renesse R, Birman K, Glade B, et al. Horus: a Flexible Group CommunicationsSystem. Ithaca, NY, USA: Cornell University,1995.
[94] Eugster P, Guerraoui R, Handurukande S, et al. Lightweight probabilistic broadcast.ACM Transaction on Computer Systems,2003,21(4):341-374.
[95] Delaet S, Ducourthial B, Tixeuil S. Tolerating transient and intermittent failures.Journal of Parallel Distribute computer.2002,62(5):961-981.
[96] Kermarrec A, Massoulie L, Ganesh A. Probabilistic Reliable Dissemination inLarge-Scale Systems. Transaction on Parallel Distribute System,2003,14(3):248-258.
[97] Joffroy B, Sylvie D, Shlomi D, and et al. Transient fault detectors. DistributedComputing,2007,20(1):39-51.
[98] Dwork C, Lynch N, Stockmeyer L.1988. Consensus in the presence of partialsynchrony. Journal of the ACM,1988,35(2):288-323.
[99] Aguilera M, Chen Wei, Toueg S. Heartbeat: a Timeout-Free Failure Detector forQuiescent Reliable Communication. Ithaca, NY, USA: Cornell University,1997.
[100] Barborak M, Dahbura A, Malek M. The Consensus problem in Fault-TolerantComputing. ACM Computing Surveys,1993,25(2):171-220.
[101] DOLEV D, DWORK C, ANCISTOCKMEYER L. On the minimal synchronismneeded for distributed consensus. Journal of ACM.1987,34(1):77-97.
[102] Dwork C, Lynch N, Stockmeyer L. Consensus in the presence of partial synchrony.Journal of the ACM.1988,35(2):288-323.
[103] Fetzer C, Cristian F. On the possibility of consensus in asynchronous systems.Proceeding of the1995Pacific Rim Int’l Symp. On Fault-Tolerance Systems.Newport Beach, CA,1995:271-280.
[104] Cristian F, Fetzer C. The Timed Asynchronous System Model. Technical ReportCSE97-519, Department of Computer Science，UCSD,1997.
[105] Ben M. Another advantage of free-choice: Completely asynchronous agreementprotocols. Proceedings of the2nd annual ACM symposium on Principles ofDistributed Computing.1983:27-30.
[106] Castro M, Liskov B. Practical Byzantine fault tolerance. Proceedings of3rd Symp.Operating Systems Design and Implementation,1999:173-186.
[107] Bracha G. An asynchronous [(n-1)/3]-resilient consensus protocol. Proceedings of3rd ACM Symp. On principles of Distributed Computing.1984:154-162.
[108] Zhang L. A new architecture for packet switching network protocols [D]. Dept.Elect. Eng. and Comput Sci., MIT,1989.
[109] Valente P. Exact GPS simulation and optimal fair scheduling with logarithmiccomplexity. IEEE/ACM Transactions on Networking.2007,15(6):1454–1466.
[110] Golestani S. A self-clocked fair queueing scheme for broadband applications.Proceedings of13th Proceedings Networking for Global Communications.1994,2:636-646.
[111] Goyal P, Vin H, Cheng H. Start-time fair queueing: a scheduling algorithm forintegrated services packet switching networks. IEEE/ACM Transactions onNetworking.1997,5(5):690-704.
[112] Stiliadis D, Varma A. Efficient fair queueing algorithms for packetswitchednetworks. IEEE/ACM Transactions on Networking.1998,6(2):175-185.
[113] Cobb J, Gouda M, El-Nahas A. Time-shift scheduling-fair scheduling of flows inhigh-speed networks. Transactions on Networking.1998,6(3):274-285.
[114] Xu J, Lipton R. On fundamental tradeoffs between delay bounds andcomputational complexity in packet scheduling algorithms. Networking,IEEE/ACM Transactions on Networking.2005,13(1):15-28.
[115] Shreedhar M, Varghese G. Efficient fair queuing using deficit round-robin.IEEE/ACM Transactions on Networking.1996,4(3):375-385.
[116] Lenzini L, Mingozzi E, and Stea G. Aliquem: a novel DRR implementation toachieve better latency and fairness at o(1) complexity. Proceedings of Tenth IEEEInternational Workshop on Quality of Service.2002:77-86.
[117] Saha D, Mukherjee S, Tripathi S. Carry-over round robin: a simple cell schedulingmechanism for ATM networks. IEEE/ACM Transactions on Networking.1998,6(6):779-796.
[118] Garg R, Chen X. RRR: recursive round robin scheduler. Proceedings of GlobalTelecommunications Conference. The Bridge to Global Integration.1998,1:422-432.
[119] Ramabhadran S, Pasquale J. The stratified round robin scheduler: Design, analysisand implementation. IEEE/ACM Transactions on Networking.2006,14(6):1362-1373.
[120] Dally W. Virtual-channel flow control. IEEE Transactions on Parallel andDistributed Systems.1992,3(2):194-205.
[121] Rexford J, Shin K. Support for multiple classes of traffic in multicomputer routers.Proceedings of the Workshop on Parallel Computer Routing and Communication.1994:116-130.
[122] Chaskar H, Madhow U. Fair Scheduling With Tunable Latency: A Round-RobinApproach. IEEE/ACM Transaction on networking.2003:11(4).
[123] Blake T, Trivedi S. Multistage interconnection network reliability. IEEETransactions on Computers.1989,38(11):1600-1604.