高性能业务路由器系统软件研究
|
摘要
目前,基于互联网的业务需求和种类与日俱增。随着互联网业务扩展到视频(如IPTV)、音频(如Voice over IP)和虚拟专用网等应用,这就要求路由器不仅仅能够完成传统的尽力而为转发,而且需要实现对多业务的有效承载。而位于网络汇聚层的高性能业务路由器是用户业务和服务提供商的接入控制点,是下一代互联网中实现有效业务控制和区分的核心设备。由于其在下一代互联网中的关键位置,业务路由器需要具备可扩展性和高可靠性,以应付网络中各种流量和应用的需求。此外,它应能够根据策略实现动态资源分配,以满足不同业务的资源需求。
业务路由器的软件体系结构决定了其灵活性和可扩展性。以往研究多基于PC架构,缺乏对实际的网络处理器系统的研究,不具备通用性和可操作性。在对具体硬件平台抽象的基础上,提出了一种用于业务路由器的可扩展路由软件系统架构(EROS-可扩展路由器操作系统)。基于模块化和层次化的结构,提出了软件转发引擎(SFE)对底层硬件转发引擎(如网络处理器)进行了屏蔽。EROS可应用于基于不同的网络处理器的业务路由器平台,解决了软件系统的跨平台要求。EROS中给出了一种分布式可靠通信机制(RCMS),结合了可靠组播和基于TCP Socket单播的机制,能够满足业务路由器内部通信对可靠性的要求。
转发处理是业务路由器数据平面的非常重要和复杂的问题。在分析了现有查找和分类技术基础上,提出一种基于策略流的转发方式。和传统的基于分组的转发方式不同,策略流转发只需要对流的首分组进行复杂的分类和查找操作,并生成全局唯一的流ID,而对该流的后续分组采用基于流ID的精确匹配即可。该机制优点在于能够提高转发速率并具备业务的可扩展性,并兼顾IPv4和IPv6网络的需求。通过建模分析了影响策略流转发性能的关键因素,给出了一种加权LRU算法用于流规则替换,并比较了用于流匹配的各种哈希查找算法。
故障恢复是软件系统的关键技术之一。通过基于连续马尔可夫链的数学模型,系统地分析了现有故障恢复策略,并对其进行了数值分析。分析表明,现有机制无法适用于不同的网络应用场景。基于此,提出了一种基于自适应的故障恢复机制,该机制可用根据场景动态选择恢复方式。实验表明,该机制能够提高系统的可用性,且导致的系统开销较小,是一种合理且有效的故障恢复策略。
带宽分配算法决定了业务路由器软件对资源分配是否有效。目前,带宽分配多基于区分服务和尽力转发模型。在分析IP网络中的带宽分配的模型的基础上,基于业务路由器的需求提出了一种通用的基于收入值的通用带宽分配模型。该模型以最优化收入值为约束条件进行动态资源分配,具备物理平台的无关性,有一定的理论创新性。从理论上证明了RBA问题与背包问题的等效,并将基于收入值的带宽分配(RBA)问题划分为灵活的RBA问题(FRBA)和严格的RBA(SRBA)问题,并证明了其与背包问题的等效。在贪婪算法的基础上,分别给出了ASRBA和AFRBA算法对SRBA和FRBA问题进行求解。实验表明,算法能够有效地对RBA问题进行求解,并能在多项式时间内完成。
在交换容量为128Gbps的业务路由器原型平台上实现并验证了上述理论和成果。它基于EROS实现可扩展的软件架构,应用了策略流机制进行数据转发,通过故障恢复策略来实现高可用性,并采用RBA算法进行带宽分配。该平台通过了国家科技部组织的专家验收,以该平台为原型的高性能路由器已获得信息产业部高端路由器入网证,并已应用于国内外的运营商网络环境中。
Recently, there has been an increased interest in expanding the set of services that Internet provides. The demand of extending the set of services, such as IPTV, Voice over IP and Virtual private Networks, represents an opportunity to extend the traditional domain of Internet routers beyond simple best-effort forwarding. High-performance service routers, lying in the network aggregation layer, are the service access points between versatile services of subscribers and service provider environment. Due to their critical position in the Next-Generation Internet (NGI), service routers should be extensible and robust when presented with unanticipated applications and workloads. They should dynamically allocate their resources across the services they support according to dynamically-established policies to ensure that each service gets the resources it needs. This dissertation studies the key issues of system software on service routers and makes four contributions.
It is the software architecture that determines the scalability and flexibility of services routers. Most of current researches build their software on the commercial off-the-shelf components(Linux, etc.) and thus lack of the exploration on the real-world NPU-based distributed routers. This dissertation presents an extensible routing software platform for services routers called EROS (Extensible Routing Operation System), which is a modularized and layered system. EROS innovatively utilizes software forwarding engine to hide concrete hardware details and thus can be used in different network processor based routers. This dissertation also describes a novel distributed reliable communication mechanism (RCMS) designed for internal communication in EROS. The RCMS combines reliable multicast and TCP-socket based uni-cast,and could satisfy the reliability requirements of internal communication.
Forwarding operation is a complex and important issue on data plane processing in services routers. The dissertation describes a novel policy based flow forwarding (PFF) mechanism designed for service routers. Unlike traditional per-packet forwarding method, PFF only performs extensive processing on the first packet of a flow, associates this flow with a policy and applies the result of this processing on subsequent packets in the flow. It is shown by model analysis that hash and flow-rule replacement algorithms determine the flow forwarding performance. Based on the theoretical result, the dissertation proposes a weighted LRU algorithm and compares different hash algorithms. The experiments on the real trace demonstrate that the proposed WLRU can increase flow rule match rate significantly.
Fault recovery is one of the key issues in software system. This dissertation systematically presents possible implementation approaches on fault recovery mechanism in service routers. It shows by continuous-time Markov chain (CTMC) model and analysis that current protection approaches could not be effectively applicable for different application scenarios. Consequently, this dissertation proposes a novel Adaptive Fault-recovery Mechanism (AFM), which could dynamically select protection schemes in different scenarios. The experiments on the test bed show AFM are more effective than current protection schemes, achieving fast fail-over without causing extra burden on the system resources.
This dissertation analyzes different bandwidth allocation (BA) models in IP networks and proposes a generic revenue-aware BA model. This dissertation classifies the RBA (Revenue-based Bandwidth Allocation) problems into SRBA (Strict RBA) and FRBA (Flexible RBA) problems. It also proves that RBA problem is equivalent to Knapsack problem and provides Enhanced Greedy Algorithms to solve it. The experiments on the service router show that the proposed algorithms are efficient and can be calculated in polynomial time.
All the proposed algorithms and schemes have been implemented on a 128Gbps prototype service router designed for National High-Tech Research and Development Plan of China (Proj. No. 2003AA121110 and 2005AA121410). The project had been checked and accepted, and the router has been licensed by China Ministry of Information Industry.
业务路由器的软件体系结构决定了其灵活性和可扩展性。以往研究多基于PC架构,缺乏对实际的网络处理器系统的研究,不具备通用性和可操作性。在对具体硬件平台抽象的基础上,提出了一种用于业务路由器的可扩展路由软件系统架构(EROS-可扩展路由器操作系统)。基于模块化和层次化的结构,提出了软件转发引擎(SFE)对底层硬件转发引擎(如网络处理器)进行了屏蔽。EROS可应用于基于不同的网络处理器的业务路由器平台,解决了软件系统的跨平台要求。EROS中给出了一种分布式可靠通信机制(RCMS),结合了可靠组播和基于TCP Socket单播的机制,能够满足业务路由器内部通信对可靠性的要求。
转发处理是业务路由器数据平面的非常重要和复杂的问题。在分析了现有查找和分类技术基础上,提出一种基于策略流的转发方式。和传统的基于分组的转发方式不同,策略流转发只需要对流的首分组进行复杂的分类和查找操作,并生成全局唯一的流ID,而对该流的后续分组采用基于流ID的精确匹配即可。该机制优点在于能够提高转发速率并具备业务的可扩展性,并兼顾IPv4和IPv6网络的需求。通过建模分析了影响策略流转发性能的关键因素,给出了一种加权LRU算法用于流规则替换,并比较了用于流匹配的各种哈希查找算法。
故障恢复是软件系统的关键技术之一。通过基于连续马尔可夫链的数学模型,系统地分析了现有故障恢复策略,并对其进行了数值分析。分析表明,现有机制无法适用于不同的网络应用场景。基于此,提出了一种基于自适应的故障恢复机制,该机制可用根据场景动态选择恢复方式。实验表明,该机制能够提高系统的可用性,且导致的系统开销较小,是一种合理且有效的故障恢复策略。
带宽分配算法决定了业务路由器软件对资源分配是否有效。目前,带宽分配多基于区分服务和尽力转发模型。在分析IP网络中的带宽分配的模型的基础上,基于业务路由器的需求提出了一种通用的基于收入值的通用带宽分配模型。该模型以最优化收入值为约束条件进行动态资源分配,具备物理平台的无关性,有一定的理论创新性。从理论上证明了RBA问题与背包问题的等效,并将基于收入值的带宽分配(RBA)问题划分为灵活的RBA问题(FRBA)和严格的RBA(SRBA)问题,并证明了其与背包问题的等效。在贪婪算法的基础上,分别给出了ASRBA和AFRBA算法对SRBA和FRBA问题进行求解。实验表明,算法能够有效地对RBA问题进行求解,并能在多项式时间内完成。
在交换容量为128Gbps的业务路由器原型平台上实现并验证了上述理论和成果。它基于EROS实现可扩展的软件架构,应用了策略流机制进行数据转发,通过故障恢复策略来实现高可用性,并采用RBA算法进行带宽分配。该平台通过了国家科技部组织的专家验收,以该平台为原型的高性能路由器已获得信息产业部高端路由器入网证,并已应用于国内外的运营商网络环境中。
Recently, there has been an increased interest in expanding the set of services that Internet provides. The demand of extending the set of services, such as IPTV, Voice over IP and Virtual private Networks, represents an opportunity to extend the traditional domain of Internet routers beyond simple best-effort forwarding. High-performance service routers, lying in the network aggregation layer, are the service access points between versatile services of subscribers and service provider environment. Due to their critical position in the Next-Generation Internet (NGI), service routers should be extensible and robust when presented with unanticipated applications and workloads. They should dynamically allocate their resources across the services they support according to dynamically-established policies to ensure that each service gets the resources it needs. This dissertation studies the key issues of system software on service routers and makes four contributions.
It is the software architecture that determines the scalability and flexibility of services routers. Most of current researches build their software on the commercial off-the-shelf components(Linux, etc.) and thus lack of the exploration on the real-world NPU-based distributed routers. This dissertation presents an extensible routing software platform for services routers called EROS (Extensible Routing Operation System), which is a modularized and layered system. EROS innovatively utilizes software forwarding engine to hide concrete hardware details and thus can be used in different network processor based routers. This dissertation also describes a novel distributed reliable communication mechanism (RCMS) designed for internal communication in EROS. The RCMS combines reliable multicast and TCP-socket based uni-cast,and could satisfy the reliability requirements of internal communication.
Forwarding operation is a complex and important issue on data plane processing in services routers. The dissertation describes a novel policy based flow forwarding (PFF) mechanism designed for service routers. Unlike traditional per-packet forwarding method, PFF only performs extensive processing on the first packet of a flow, associates this flow with a policy and applies the result of this processing on subsequent packets in the flow. It is shown by model analysis that hash and flow-rule replacement algorithms determine the flow forwarding performance. Based on the theoretical result, the dissertation proposes a weighted LRU algorithm and compares different hash algorithms. The experiments on the real trace demonstrate that the proposed WLRU can increase flow rule match rate significantly.
Fault recovery is one of the key issues in software system. This dissertation systematically presents possible implementation approaches on fault recovery mechanism in service routers. It shows by continuous-time Markov chain (CTMC) model and analysis that current protection approaches could not be effectively applicable for different application scenarios. Consequently, this dissertation proposes a novel Adaptive Fault-recovery Mechanism (AFM), which could dynamically select protection schemes in different scenarios. The experiments on the test bed show AFM are more effective than current protection schemes, achieving fast fail-over without causing extra burden on the system resources.
This dissertation analyzes different bandwidth allocation (BA) models in IP networks and proposes a generic revenue-aware BA model. This dissertation classifies the RBA (Revenue-based Bandwidth Allocation) problems into SRBA (Strict RBA) and FRBA (Flexible RBA) problems. It also proves that RBA problem is equivalent to Knapsack problem and provides Enhanced Greedy Algorithms to solve it. The experiments on the service router show that the proposed algorithms are efficient and can be calculated in polynomial time.
All the proposed algorithms and schemes have been implemented on a 128Gbps prototype service router designed for National High-Tech Research and Development Plan of China (Proj. No. 2003AA121110 and 2005AA121410). The project had been checked and accepted, and the router has been licensed by China Ministry of Information Industry.
引文
[1] Zeadally S., Siddiqui F., Kubher P. Voice over IP in intranet and internet environments. IEE Proceedings: Communications, 2004, 151(3): 263~269
[2] Davies C. 2005: The year of IPTV, Journal of the Communication Network, 2005,4: 4~7
[3] Multiple-Services Rings based on RPR. ITU-T Recommendation X.87, 2004
[4] Jajszczyk A. IP for 3G, Networking Technologies for Mobile Communications. IEEE Communications Magazine, 2003, 41(11): 8~10
[5] General overview of NGN. ITU-T Recommendation Y.2001, 2004
[6] Aweya J. IP router architectures: an overview. International Journal of Communication Systems, 2001, 14 (5): 447~475
[7] O'Riordan M. Router evolution: The "service router". Elektron, 2004, 21(3): 36~37
[8] Rosen E.,Rekhter Y. BGP/MPLS VPNs. IETF RFC 2547, March 1999
[9] Kent S., Atkinson R. Security Architecture for the Internet Protocol. IETF RFC2041, November 1998
[10] 徐建锋, 张大炜, 毕诗章. 互联网技术的发展趋势和中国电信 CN2 实践. 电信科学, 2005(5): 1~5
[11] Reeve M. H., Bilton C., Holmes P. E., et al. 21cn Networks and systems for BT in the 21st century. BT Technology Journal, 2005, 23(1):11~14
[12] Kuhns F., Dehart J., Keller R., et al. Implementation of an Open Multi-Service Router. Technical Report WUCS-01-20, Washington University, August 2001
[13] Tellabs Multi-Service Router Datasheet. Tellabs, 2004. http://www.tellabs.com
[14] Alcatel 7750 Service Router Datasheet. Alcatel, 2005. http://www.alcatel.com
[15] Juniper Network E320 Service Router Datasheet. Juniper Networks, 2005. http://www.juniper.net
[16] Katsumata K., Iwano T., Ono M., et al. New service feature of carrier class edge router "IX5010/5020". NEC Research and Development, 2001, 42(2): 110~113
[17] Chan Ben C.B., Lau John C.F., Lui John C.S. OPERA: An open-source extensiblerouter architecture for adding new network services and protocols. Journal of Systems and Software, 2005, 78(1): 24~36
[18] Xu Ke, Xu Mingwei, Wu Jianping. Research on software architecture of the extensible services router. High Technology Letters, 2002, 8(2): 35~38
[19] Ruf L., Keller R., Plattner B. A scalable high-performance router platform supporting dynamic service extensibility on network and host processors. In: Proceedings-The IEEE/ACS International Conference on Pervasive Services 2004. 2004: 199~206
[20] Gao J., Steenkiste P., Takahashi E., et al. Programmable router architecture supporting control plane extensibility. IEEE Communications Magazine, 2000, 38(3): 152~159
[21] Douglas E. Comer. Network systems design using network processors. New Jersey: Prentice Hall, 2003.
[22] Franklin M. A., Crowley P., Hadimioglu H., et al. Network processor design issues and practices. Boston: Morgan Kaufmann Publishers, 2003
[23] 陈震. 可伸展多级分组交换网络结构的研究: [博士学位论文]. 西安电子科技大学, 2004
[24] Chao, H.J. Next generation routers. Proceedings of the IEEE, 2002, 90(9): 1518~1558
[25] Sundar I., McKeown N. Analysis of the parallel packet switch architecture. IEEE/ACM Transactions on Networking, 2003, 11(2): 314~324
[26] McKeown N. iSLIP: A scheduling algorithm for input-queued switches. IEEE/ACM Transactions on Networking, 1999, 7(2): 188~201
[27] Nilsson S., Karlsson G. IP-Address lookup using LC-tries. IEEE Journal on Selected Areas in Communications, 1999, 17(6): 1083~1092
[28] Gupta A., Mckeown N. Packet classification on multiple fields. ACM Computer Review, 1999, 29(4): 146~160
[29] Woo T.Y.C. A modular approach to packet classification: algorithms and results. In: Proceeding of IEEE Infocom 2000. 2000:1210~1217
[30] Huang C. C., Owens K., Makam S. Building reliable MPLS networks using a path protection mechanism. IEEE Communications Magazine, 2002, 40(3): 156~162
[31] IP Unicast Forwarding Services API Implementation Agreement, Network Processor Forum, June 2004. http://www.npforum.com
[32] Stream Interface Implementation Agreement, Network Processor Forum, October 2002. http://www.npforum.com
[33] IXP1200 Network Processor Datasheet. Intel Corporation, 2000. http://www.intel.com
[34] IBM PowerNP NP4G3 Network Processor Solution Product Overview, IBM Microelectronics Division, April 2001. http://www.ibm.com
[35] NP-1c Network Processor. Ezchip Technologies, 2004. http://www.ezchip.com
[36] Decasper D., Dittia Z., Parulkar G., et al. Router Plugins: A software architecture for next generation routers. IEEE/ACM Transactions on Networks, 2000, 8(1): 2-15
[37] Karlin S., Peterson L. VERA: an extensible router architecture. In: Proceedings of the 4th Internal Conference on Open Architectures and Network Programming (OPENARCH), 2001: 3~14
[38] Hjalmtysson G., Bhattacharjee S. Control-on-Demand: An Efficient Approach to Router Programmability. IEEE Journal on Selected Areas in Communications, 1999, 17(9): 1549~1562
[39] Louati W., Jouaber B., Zeghlache D. Configurable software-based edge router architecture. Computer Communications, 2005, 28 (14): 1692~1699
[40] Kounavis M. E., Campell A. T., Chou S., et al. The genesis kernel: a programming system for spawning network architectures. IEEE Journal on Selected Areas in Communications, 2001, 19(3): 511-526
[41] Handley M., Hodson O., Kohler E. XORP: An Open Platform for Network Research. Computer Communication Review, 2003, 33(1): 53~57
[42] Rose E., Viswanathan A., Callon R. Mulitprotocol Label Switching Architecture. IETF RFC3031, 2001
[43] Bollapragada V., Murphy C., White R. Inside Cisco IOS software architecture.Indianapolis: Cisco Press, 2000
[44] Khosravi H., Anderson T. Requirements for separation of IP control and forwarding. IETF RFC3654, November 2003
[45] Bux W., Denzel W. E., Engbersen T., et al. Technologies and building blocks for fast packet forwarding. IEEE Communications Magazine, 2001, 39(1): 70-77
[46] Yang L., Halpern J., Gopal R., et al. FORCES forwarding element model. IETF draft (work in progress), August 2005
[47] Levine, B.N., Garcia-Luna-Aceves, J.J. A comparison of reliable multicast protocols. Multimedia Systems, 1998, 6(5): 334~348
[48] Yamamoto K., Sawa Y., Yamamoto M. Performance evaluation of ACK-based and NAK-based flow control mechanisms for reliable multicast communications. IEICE Transactions on Communications, 2001, E84-B (8): 2313~2316
[49] Lin J. C., Paul S. RMTP: A reliable multicast transport protocol. In: Proceeding of IEEE Infocom 1996, 1996: 1414~1425
[50] 王斌, 刘增基, 李红滨等. 基于ACK和NAK的可靠组播传输协议的性能分析和比较. 电子学报, 2001, 29(10): 1314~1318
[51] Ramakrishna, S.T.G.S., Jamadagni, H.S. Analytical bounds on the threads in IXP1200 network processor. In: Proceedings of Euromicro Symposium on Digital System Design 2003. 2003: 426~429
[52] Bernardinis F., Fanucci L., Ramacciotti T., et al. A QoS Internet protocol scheduler on the IXP1200 network platform. In: Proceedings of the 3rd IEEE International Workshop on System-on-Chip for Real-Time Applications. 2003:394~399
[53] Niraj S., Plishker W., Kaushik R., et al. NP-Click: a productive software development approach for network processors. IEEE Micro, 2004, 24(5): 45~54
[54] PrPMC800: MPC7410 Processor PMC with AltiVec Technology. Motorola Inc. http://www.motolora.com
[55] VxWorks Real-time Operation System. Windriver Systems, 2003. http://www.windriver.com
[56] Agilient N2X Brochure. Agilient Technologies, 2004. http://www.agilient.com.
[57] Simpson W. The point-to-point protocol (PPP). IETF RFC 1548, 1993
[58] Ravikumar V. C., Mahapatra R. N. TCAM architecture for IP lookup using prefix properties. IEEE Micro, 2004, 24(2): 60~69
[59] Shah D., Cupta P. Fast updating algorithms for TCAM. IEEE Micro, 2001, 21(1): 36~47
[60] Waldvogel M., Varghese G., Turner J., et al. Scalable high speed IP routing lookups. In: Proceedings of ACM SIGCOMM 97, 1997: 25~36
[61] Chang Y. K. A small and fast IP forwarding table using hashing. IEICE Transactions on communication, 2005, E88-B (1): 239~246
[62] Knuth D. Fundamental Algorithms: Sorting and Searching. MA: Addison-Wesley, 1973
[63] Kijkanjanarat T. Fast routing lookup and packet classification for next-generation routers. [Ph.D. dissertation]: Polytechnic University, Brooklyn, NY, 2002
[64] Sahni S., Kim K. S. Efficient construction of multibit tries for IP lookup. IEEE/ACM Transactions on Networking, 2003, 11(4): 650~662
[65] Ravikumar V. C., Mahapatra R. N., Liu L. C. Modified LC-Trie Based Efficient Routing Lookup. In: Proceedings of MASCOTS 2002, 2002:177-182
[66] Gupta P., Lin S., McKeown N. Routing lookups in hardware at memory access speeds. In: Proceedings of IEEE INFOCOM '98, 1998: 1240~1247
[67] Srinivasan V., Varghese G., Suri S., et al. Fast and scalable layer four switching. In: Proceedings of ACM Sigcomm’ 98, 1998: 203~214
[68] Xu K., et al. A non-collision Hash trie-tree based IP classification algorithm. Journal of Computer and Science Technology, 2002, 17(2): 219~226
[69] Shang F. J., Pan Y. J. An absolute non-collision hash algorithm. In: Proceeding of Third International Conference on Machine Learning and Cybernetics, 2004: 2592~2595, Shanghai, China
[70] Carrier Routing System Technical Paper. Cisco Systems, 2004. http://www.cisco.com
[71] Kim M. S., et al. Application-level traffic monitoring and an analysis on IP networks. ETRI journal, 2005, 27(1): 1~21
[72] Sen S., et al. Accurate, scalable, in-network identification of P2P traffic using application signatures. In: Proceedings of WWW2004, 2004: 512~521, New York
[73] Mckeown N. Packet switch architecture II: address lookup and classification. EE384Y Lecture Notes. Stanford University, 2004. http://www. stanford. edu/~nickm
[74] Newman P., Minshall G., Lyon T. IP switching: ATM under IP. IEEE/ACM Transactions on Networking, 1998, 6(2): 117~129
[75] IP Navigator MPLS Technical Paper. Lucent Technologies, 1999. http://www.lucent.com
[76] Katsube Y., et al. Toshiba's Router Architecture Extensions for ATM: Overview. IETF RFC 2098, 1997
[77] Cisco Tag Switching White Paper. Cisco Systems, 1998. http://www.cisco.com
[78] Pablo M.F. Circuit Switching in the Internet. [PH.D dissertation]: Stanford University, 2003
[79] NLANR network trace packet header traces. NLANR, 2004. htttp://moat.nlanr.net
[80] Grizzard J. B., et al. Flow based observations from NETI@home and Honeynet data. In: Proceedings of 2005 IEEE workshop on Information Assurance and Security, 2005: 244~251
[81] Brownlee N., Claffy K. Understanding Internet traffic streams: dragonflies and tortoises. IEEE Communications Magazine, 2002, 40(10): 110~117
[82] Zseby T., Molina M., Duffield N., et al. Sampling and Filtering Techniques for IP Packet Selection. IETF draft (working in progress), 2005
[83] 程光, 龚俭, 丁伟等. 面向 IP 流测量的哈希算法研究. 软件学报, 2005, 16(5): 652~658
[84] Cao Z., Wang Z., Zegura E. Performance of hashing-based schemes for Internet load balancing. In: Proceedings of the IEEE INFOCOM 2000, 2000: 332~341
[85] Xu J., Singhal M. Cost-effective flow table designs for high-speed routers: architecture and performance evaluation. IEEE Transactions on Computer, 2002, 51(9): 1089~1099
[86] Carrier requirements of core IP routers. BTexact Technologies Whitepaper, February 2002
[87] Core competence: New Requirements for core routing. The Yankee Group, April2002
[88] Pradhan D. K. Fault-tolerant computer system design. New Jersey: Prentice-Hall, First Edition, 1996
[89] Siewiorek D., Swartz R. The theory and practice of reliable system design Wellesley: A. K. Peters, Third Edition, 1999
[90] Keshav S., Sharma R. Issues and trends in router design. IEEE Communications Magazine, 1998, 36(5): 144~151
[91] Partridge C., Carvey P. P., Burgess E. A 50-Gb/s IP router. IEEE/ACM Transactions on Networking, 1998, 6(3): 237~243
[92] Trived K. Probability and statistics with reliability, queuing, and computer science applications. New York: John Wiley and Sons, New Edition, 2001
[93] Shooman M. L. Reliability of computer systems and networks: fault tolerance, analysis, and design. New York: John Wiley and Sons, 2002
[94] 徐恪, 吴建平, 吴剑等. 高性能路由器操作系统 HEROS 中的高可用性设计. 高技术通讯, 2002, 12(9): 1~6
[95] Russ W. High availability in routing. The Internet Protocol Journal, 2004, 7(1): 2~15
[96] Gupta M. Designing a stable highly available router for new service deployment. Redback Networks, 2002. http://www.redback.com
[97] Cisco Nonstop Forwarding Whitepaper. Cisco Systems. 2003. http://www.cisco.com
[98] Leelanivas M., Rekhter Y., Aggarwal R. Graceful restart mechanism for label distribution protocol. IEEE RFC 3478, Feb 2003
[99] Moy J., Pillay-Esnault P., Lindem A. graceful OSPF restart. IETF RFC 3623, Nov 2003
[100] Knight S., Weaver D., Whipple D., et al. Virtual router redundancy protocol (VRRP). IETF RFC 2338, April 1998
[101] Li T., Cole B., Morton P., et al. Cisco Hot Standby Router Protocol. IETF RFC 2281, Mar 1998
[102] Gouda M.G., McGuire T. M. Accelerated heartbeat protocols.In: Proceedings of 18th Inl’ Conference on Distributed Computing Systems. 1998: 202~209
[103] 史树明, 温冬婵, 沈美明等. 分布式文件系统低耦合度高可用性支持模块的实现. 计算机研究与发展, 2003, 40(8): 1258~1264
[104] Noel B. K. HotSwap – transparent server failover for Linux. In: Proceedings of USENIX LISA 2002, 2002: 205~212
[105] Xie M., Dai Y. S., Poh K. L. Computing system reliability: models and analysis. New York: Kluwer Academic/Plenum Publishers, 2004
[106] David I H. Dependability Modeling for Computer Systems. In: Proceedings of Annual Reliability and Maintainability Symposium’1991, 1991: 120~128
[107] Dugan J. B., Trivedi K S. Coverage modeling for dependability analysis of fault-tolerant systems. IEEE Transactions on Computers, 1989, 38(6): 775~787
[108] Postel J. Internet protocol. IETF RFC791, September 1981
[109] Braden R., Zhang L., Berson S., et al. Resource reservation protocol. IETF RFC2205, September 1997
[110] S. Blake, Black D., Carlson M., et al. An architecture for differentiated service. IETF RFC2475, December 1998
[111] Chen Y. J., Lee S. Y. An efficient scheme to achieve weighted max-min fairness on bandwidth allocation. Journal of Information & Optimization Sciences, 2003, 24(2): 211~237
[112] Park E. C., Choi C. H. Proportional bandwidth allocation in diffServ networks. In: Proceedings of IEEE INFOCOM 2004, 2004: 2038 ~2049
[113] 隆克平等. 区分服务结构及其 TCP 性能分析. 电子学报, 2001, 29(11): 1540 ~1545, 1548
[114] Fernandez M.P., Pedroza A.De.C.P., Rezende J.F.De. Dynamic QoS provisioning in DiffServ domains using fuzzy logic controllers. Telecommunication Systems - Modeling, Analysis, Design and Management, 2004, 26(1): 9~32
[115] Li, J. S., Mao, C. S. Providing flow-based proportional differentiated services in class-based DiffServ routers. IEE Proceedings-Communications, 2004, 151(1): 82~88
[116] Hatano T., Shigeno H., Okada, K.I., et al. Fair bandwidth allocation in diffserv networks. Transactions of the Information Processing Society of Japan, 2004, 45(12): 2773~2781
[117] 刘正蓝, 朱淼良, 汤旭红. 区分服务网络中带宽利用的公平性. 计算机学报, 2004, 27(1): 107~114
[118] Lidl J., Evarts D., Carrel D., et al. Method for transmitting PPP over Ethernet (PPPoE). IETF RFC 2615, February 1999
[119] Qiu Y., Marbach P. Bandwidth allocation in Ad-Hoc networks: A Price-Based Approach. In: Proceedings of IEEE INFOCOM 2003, 2003: 797~807
[120] Joutsensalo J., Hamalainen T. Optimal link allocation and revenue maximization. Journal of Communications and Networks, 2002, 4(2): 136~147
[121] Zhang J., Hamalainen T., J. Joutsensalo. Revenue-aware resource allocation Scheme in multiservice IP networks. WSEAS Transactions on Communications, 2004, 1 (3): 277~281
[122] Resilient packet ring (RPR) access method & physical layer specifications. IEEE Standard P802.17, 2004
[123] Rigney C., Rubens A., Simpson W., et al. Remote Authentication Dial In User Service (RADIUS). IETF RFC 2865, 2000
[124] Garey M. J., Johnson D. S. Computers and intractability: a guide to the theory of NP-Completeness. San Franscisco: Freeman, 1979
[125] Martello S., Pisinger D., Toth P. Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Science, 1999, 45(3): 414 ~ 424
[126] Martello S., Pisinger D., Toth P. New trends in exact algorithms for the 0-1 knapsack problem. European Journal of Operational Research, 2000: 325 ~332
[127] Horowitz E., Sahni S. Computing partitions with applications to the knapsack problem. Journal of ACM, 1974, 21(2): 277~292
[128] Ferreira A. G., A parallel time/hardware tradeoff T.H= O (2 n/2) for the knapsack problem. IEEE Transactions on Computers, 1994, 40(2): 221~225.
[129] Karnin E. D. A parallel algorithm for the knapsack problem. IEEE Transactions on Computers, 1984, 33 (5): 404 ~408
[2] Davies C. 2005: The year of IPTV, Journal of the Communication Network, 2005,4: 4~7
[3] Multiple-Services Rings based on RPR. ITU-T Recommendation X.87, 2004
[4] Jajszczyk A. IP for 3G, Networking Technologies for Mobile Communications. IEEE Communications Magazine, 2003, 41(11): 8~10
[5] General overview of NGN. ITU-T Recommendation Y.2001, 2004
[6] Aweya J. IP router architectures: an overview. International Journal of Communication Systems, 2001, 14 (5): 447~475
[7] O'Riordan M. Router evolution: The "service router". Elektron, 2004, 21(3): 36~37
[8] Rosen E.,Rekhter Y. BGP/MPLS VPNs. IETF RFC 2547, March 1999
[9] Kent S., Atkinson R. Security Architecture for the Internet Protocol. IETF RFC2041, November 1998
[10] 徐建锋, 张大炜, 毕诗章. 互联网技术的发展趋势和中国电信 CN2 实践. 电信科学, 2005(5): 1~5
[11] Reeve M. H., Bilton C., Holmes P. E., et al. 21cn Networks and systems for BT in the 21st century. BT Technology Journal, 2005, 23(1):11~14
[12] Kuhns F., Dehart J., Keller R., et al. Implementation of an Open Multi-Service Router. Technical Report WUCS-01-20, Washington University, August 2001
[13] Tellabs Multi-Service Router Datasheet. Tellabs, 2004. http://www.tellabs.com
[14] Alcatel 7750 Service Router Datasheet. Alcatel, 2005. http://www.alcatel.com
[15] Juniper Network E320 Service Router Datasheet. Juniper Networks, 2005. http://www.juniper.net
[16] Katsumata K., Iwano T., Ono M., et al. New service feature of carrier class edge router "IX5010/5020". NEC Research and Development, 2001, 42(2): 110~113
[17] Chan Ben C.B., Lau John C.F., Lui John C.S. OPERA: An open-source extensiblerouter architecture for adding new network services and protocols. Journal of Systems and Software, 2005, 78(1): 24~36
[18] Xu Ke, Xu Mingwei, Wu Jianping. Research on software architecture of the extensible services router. High Technology Letters, 2002, 8(2): 35~38
[19] Ruf L., Keller R., Plattner B. A scalable high-performance router platform supporting dynamic service extensibility on network and host processors. In: Proceedings-The IEEE/ACS International Conference on Pervasive Services 2004. 2004: 199~206
[20] Gao J., Steenkiste P., Takahashi E., et al. Programmable router architecture supporting control plane extensibility. IEEE Communications Magazine, 2000, 38(3): 152~159
[21] Douglas E. Comer. Network systems design using network processors. New Jersey: Prentice Hall, 2003.
[22] Franklin M. A., Crowley P., Hadimioglu H., et al. Network processor design issues and practices. Boston: Morgan Kaufmann Publishers, 2003
[23] 陈震. 可伸展多级分组交换网络结构的研究: [博士学位论文]. 西安电子科技大学, 2004
[24] Chao, H.J. Next generation routers. Proceedings of the IEEE, 2002, 90(9): 1518~1558
[25] Sundar I., McKeown N. Analysis of the parallel packet switch architecture. IEEE/ACM Transactions on Networking, 2003, 11(2): 314~324
[26] McKeown N. iSLIP: A scheduling algorithm for input-queued switches. IEEE/ACM Transactions on Networking, 1999, 7(2): 188~201
[27] Nilsson S., Karlsson G. IP-Address lookup using LC-tries. IEEE Journal on Selected Areas in Communications, 1999, 17(6): 1083~1092
[28] Gupta A., Mckeown N. Packet classification on multiple fields. ACM Computer Review, 1999, 29(4): 146~160
[29] Woo T.Y.C. A modular approach to packet classification: algorithms and results. In: Proceeding of IEEE Infocom 2000. 2000:1210~1217
[30] Huang C. C., Owens K., Makam S. Building reliable MPLS networks using a path protection mechanism. IEEE Communications Magazine, 2002, 40(3): 156~162
[31] IP Unicast Forwarding Services API Implementation Agreement, Network Processor Forum, June 2004. http://www.npforum.com
[32] Stream Interface Implementation Agreement, Network Processor Forum, October 2002. http://www.npforum.com
[33] IXP1200 Network Processor Datasheet. Intel Corporation, 2000. http://www.intel.com
[34] IBM PowerNP NP4G3 Network Processor Solution Product Overview, IBM Microelectronics Division, April 2001. http://www.ibm.com
[35] NP-1c Network Processor. Ezchip Technologies, 2004. http://www.ezchip.com
[36] Decasper D., Dittia Z., Parulkar G., et al. Router Plugins: A software architecture for next generation routers. IEEE/ACM Transactions on Networks, 2000, 8(1): 2-15
[37] Karlin S., Peterson L. VERA: an extensible router architecture. In: Proceedings of the 4th Internal Conference on Open Architectures and Network Programming (OPENARCH), 2001: 3~14
[38] Hjalmtysson G., Bhattacharjee S. Control-on-Demand: An Efficient Approach to Router Programmability. IEEE Journal on Selected Areas in Communications, 1999, 17(9): 1549~1562
[39] Louati W., Jouaber B., Zeghlache D. Configurable software-based edge router architecture. Computer Communications, 2005, 28 (14): 1692~1699
[40] Kounavis M. E., Campell A. T., Chou S., et al. The genesis kernel: a programming system for spawning network architectures. IEEE Journal on Selected Areas in Communications, 2001, 19(3): 511-526
[41] Handley M., Hodson O., Kohler E. XORP: An Open Platform for Network Research. Computer Communication Review, 2003, 33(1): 53~57
[42] Rose E., Viswanathan A., Callon R. Mulitprotocol Label Switching Architecture. IETF RFC3031, 2001
[43] Bollapragada V., Murphy C., White R. Inside Cisco IOS software architecture.Indianapolis: Cisco Press, 2000
[44] Khosravi H., Anderson T. Requirements for separation of IP control and forwarding. IETF RFC3654, November 2003
[45] Bux W., Denzel W. E., Engbersen T., et al. Technologies and building blocks for fast packet forwarding. IEEE Communications Magazine, 2001, 39(1): 70-77
[46] Yang L., Halpern J., Gopal R., et al. FORCES forwarding element model. IETF draft (work in progress), August 2005
[47] Levine, B.N., Garcia-Luna-Aceves, J.J. A comparison of reliable multicast protocols. Multimedia Systems, 1998, 6(5): 334~348
[48] Yamamoto K., Sawa Y., Yamamoto M. Performance evaluation of ACK-based and NAK-based flow control mechanisms for reliable multicast communications. IEICE Transactions on Communications, 2001, E84-B (8): 2313~2316
[49] Lin J. C., Paul S. RMTP: A reliable multicast transport protocol. In: Proceeding of IEEE Infocom 1996, 1996: 1414~1425
[50] 王斌, 刘增基, 李红滨等. 基于ACK和NAK的可靠组播传输协议的性能分析和比较. 电子学报, 2001, 29(10): 1314~1318
[51] Ramakrishna, S.T.G.S., Jamadagni, H.S. Analytical bounds on the threads in IXP1200 network processor. In: Proceedings of Euromicro Symposium on Digital System Design 2003. 2003: 426~429
[52] Bernardinis F., Fanucci L., Ramacciotti T., et al. A QoS Internet protocol scheduler on the IXP1200 network platform. In: Proceedings of the 3rd IEEE International Workshop on System-on-Chip for Real-Time Applications. 2003:394~399
[53] Niraj S., Plishker W., Kaushik R., et al. NP-Click: a productive software development approach for network processors. IEEE Micro, 2004, 24(5): 45~54
[54] PrPMC800: MPC7410 Processor PMC with AltiVec Technology. Motorola Inc. http://www.motolora.com
[55] VxWorks Real-time Operation System. Windriver Systems, 2003. http://www.windriver.com
[56] Agilient N2X Brochure. Agilient Technologies, 2004. http://www.agilient.com.
[57] Simpson W. The point-to-point protocol (PPP). IETF RFC 1548, 1993
[58] Ravikumar V. C., Mahapatra R. N. TCAM architecture for IP lookup using prefix properties. IEEE Micro, 2004, 24(2): 60~69
[59] Shah D., Cupta P. Fast updating algorithms for TCAM. IEEE Micro, 2001, 21(1): 36~47
[60] Waldvogel M., Varghese G., Turner J., et al. Scalable high speed IP routing lookups. In: Proceedings of ACM SIGCOMM 97, 1997: 25~36
[61] Chang Y. K. A small and fast IP forwarding table using hashing. IEICE Transactions on communication, 2005, E88-B (1): 239~246
[62] Knuth D. Fundamental Algorithms: Sorting and Searching. MA: Addison-Wesley, 1973
[63] Kijkanjanarat T. Fast routing lookup and packet classification for next-generation routers. [Ph.D. dissertation]: Polytechnic University, Brooklyn, NY, 2002
[64] Sahni S., Kim K. S. Efficient construction of multibit tries for IP lookup. IEEE/ACM Transactions on Networking, 2003, 11(4): 650~662
[65] Ravikumar V. C., Mahapatra R. N., Liu L. C. Modified LC-Trie Based Efficient Routing Lookup. In: Proceedings of MASCOTS 2002, 2002:177-182
[66] Gupta P., Lin S., McKeown N. Routing lookups in hardware at memory access speeds. In: Proceedings of IEEE INFOCOM '98, 1998: 1240~1247
[67] Srinivasan V., Varghese G., Suri S., et al. Fast and scalable layer four switching. In: Proceedings of ACM Sigcomm’ 98, 1998: 203~214
[68] Xu K., et al. A non-collision Hash trie-tree based IP classification algorithm. Journal of Computer and Science Technology, 2002, 17(2): 219~226
[69] Shang F. J., Pan Y. J. An absolute non-collision hash algorithm. In: Proceeding of Third International Conference on Machine Learning and Cybernetics, 2004: 2592~2595, Shanghai, China
[70] Carrier Routing System Technical Paper. Cisco Systems, 2004. http://www.cisco.com
[71] Kim M. S., et al. Application-level traffic monitoring and an analysis on IP networks. ETRI journal, 2005, 27(1): 1~21
[72] Sen S., et al. Accurate, scalable, in-network identification of P2P traffic using application signatures. In: Proceedings of WWW2004, 2004: 512~521, New York
[73] Mckeown N. Packet switch architecture II: address lookup and classification. EE384Y Lecture Notes. Stanford University, 2004. http://www. stanford. edu/~nickm
[74] Newman P., Minshall G., Lyon T. IP switching: ATM under IP. IEEE/ACM Transactions on Networking, 1998, 6(2): 117~129
[75] IP Navigator MPLS Technical Paper. Lucent Technologies, 1999. http://www.lucent.com
[76] Katsube Y., et al. Toshiba's Router Architecture Extensions for ATM: Overview. IETF RFC 2098, 1997
[77] Cisco Tag Switching White Paper. Cisco Systems, 1998. http://www.cisco.com
[78] Pablo M.F. Circuit Switching in the Internet. [PH.D dissertation]: Stanford University, 2003
[79] NLANR network trace packet header traces. NLANR, 2004. htttp://moat.nlanr.net
[80] Grizzard J. B., et al. Flow based observations from NETI@home and Honeynet data. In: Proceedings of 2005 IEEE workshop on Information Assurance and Security, 2005: 244~251
[81] Brownlee N., Claffy K. Understanding Internet traffic streams: dragonflies and tortoises. IEEE Communications Magazine, 2002, 40(10): 110~117
[82] Zseby T., Molina M., Duffield N., et al. Sampling and Filtering Techniques for IP Packet Selection. IETF draft (working in progress), 2005
[83] 程光, 龚俭, 丁伟等. 面向 IP 流测量的哈希算法研究. 软件学报, 2005, 16(5): 652~658
[84] Cao Z., Wang Z., Zegura E. Performance of hashing-based schemes for Internet load balancing. In: Proceedings of the IEEE INFOCOM 2000, 2000: 332~341
[85] Xu J., Singhal M. Cost-effective flow table designs for high-speed routers: architecture and performance evaluation. IEEE Transactions on Computer, 2002, 51(9): 1089~1099
[86] Carrier requirements of core IP routers. BTexact Technologies Whitepaper, February 2002
[87] Core competence: New Requirements for core routing. The Yankee Group, April2002
[88] Pradhan D. K. Fault-tolerant computer system design. New Jersey: Prentice-Hall, First Edition, 1996
[89] Siewiorek D., Swartz R. The theory and practice of reliable system design Wellesley: A. K. Peters, Third Edition, 1999
[90] Keshav S., Sharma R. Issues and trends in router design. IEEE Communications Magazine, 1998, 36(5): 144~151
[91] Partridge C., Carvey P. P., Burgess E. A 50-Gb/s IP router. IEEE/ACM Transactions on Networking, 1998, 6(3): 237~243
[92] Trived K. Probability and statistics with reliability, queuing, and computer science applications. New York: John Wiley and Sons, New Edition, 2001
[93] Shooman M. L. Reliability of computer systems and networks: fault tolerance, analysis, and design. New York: John Wiley and Sons, 2002
[94] 徐恪, 吴建平, 吴剑等. 高性能路由器操作系统 HEROS 中的高可用性设计. 高技术通讯, 2002, 12(9): 1~6
[95] Russ W. High availability in routing. The Internet Protocol Journal, 2004, 7(1): 2~15
[96] Gupta M. Designing a stable highly available router for new service deployment. Redback Networks, 2002. http://www.redback.com
[97] Cisco Nonstop Forwarding Whitepaper. Cisco Systems. 2003. http://www.cisco.com
[98] Leelanivas M., Rekhter Y., Aggarwal R. Graceful restart mechanism for label distribution protocol. IEEE RFC 3478, Feb 2003
[99] Moy J., Pillay-Esnault P., Lindem A. graceful OSPF restart. IETF RFC 3623, Nov 2003
[100] Knight S., Weaver D., Whipple D., et al. Virtual router redundancy protocol (VRRP). IETF RFC 2338, April 1998
[101] Li T., Cole B., Morton P., et al. Cisco Hot Standby Router Protocol. IETF RFC 2281, Mar 1998
[102] Gouda M.G., McGuire T. M. Accelerated heartbeat protocols.In: Proceedings of 18th Inl’ Conference on Distributed Computing Systems. 1998: 202~209
[103] 史树明, 温冬婵, 沈美明等. 分布式文件系统低耦合度高可用性支持模块的实现. 计算机研究与发展, 2003, 40(8): 1258~1264
[104] Noel B. K. HotSwap – transparent server failover for Linux. In: Proceedings of USENIX LISA 2002, 2002: 205~212
[105] Xie M., Dai Y. S., Poh K. L. Computing system reliability: models and analysis. New York: Kluwer Academic/Plenum Publishers, 2004
[106] David I H. Dependability Modeling for Computer Systems. In: Proceedings of Annual Reliability and Maintainability Symposium’1991, 1991: 120~128
[107] Dugan J. B., Trivedi K S. Coverage modeling for dependability analysis of fault-tolerant systems. IEEE Transactions on Computers, 1989, 38(6): 775~787
[108] Postel J. Internet protocol. IETF RFC791, September 1981
[109] Braden R., Zhang L., Berson S., et al. Resource reservation protocol. IETF RFC2205, September 1997
[110] S. Blake, Black D., Carlson M., et al. An architecture for differentiated service. IETF RFC2475, December 1998
[111] Chen Y. J., Lee S. Y. An efficient scheme to achieve weighted max-min fairness on bandwidth allocation. Journal of Information & Optimization Sciences, 2003, 24(2): 211~237
[112] Park E. C., Choi C. H. Proportional bandwidth allocation in diffServ networks. In: Proceedings of IEEE INFOCOM 2004, 2004: 2038 ~2049
[113] 隆克平等. 区分服务结构及其 TCP 性能分析. 电子学报, 2001, 29(11): 1540 ~1545, 1548
[114] Fernandez M.P., Pedroza A.De.C.P., Rezende J.F.De. Dynamic QoS provisioning in DiffServ domains using fuzzy logic controllers. Telecommunication Systems - Modeling, Analysis, Design and Management, 2004, 26(1): 9~32
[115] Li, J. S., Mao, C. S. Providing flow-based proportional differentiated services in class-based DiffServ routers. IEE Proceedings-Communications, 2004, 151(1): 82~88
[116] Hatano T., Shigeno H., Okada, K.I., et al. Fair bandwidth allocation in diffserv networks. Transactions of the Information Processing Society of Japan, 2004, 45(12): 2773~2781
[117] 刘正蓝, 朱淼良, 汤旭红. 区分服务网络中带宽利用的公平性. 计算机学报, 2004, 27(1): 107~114
[118] Lidl J., Evarts D., Carrel D., et al. Method for transmitting PPP over Ethernet (PPPoE). IETF RFC 2615, February 1999
[119] Qiu Y., Marbach P. Bandwidth allocation in Ad-Hoc networks: A Price-Based Approach. In: Proceedings of IEEE INFOCOM 2003, 2003: 797~807
[120] Joutsensalo J., Hamalainen T. Optimal link allocation and revenue maximization. Journal of Communications and Networks, 2002, 4(2): 136~147
[121] Zhang J., Hamalainen T., J. Joutsensalo. Revenue-aware resource allocation Scheme in multiservice IP networks. WSEAS Transactions on Communications, 2004, 1 (3): 277~281
[122] Resilient packet ring (RPR) access method & physical layer specifications. IEEE Standard P802.17, 2004
[123] Rigney C., Rubens A., Simpson W., et al. Remote Authentication Dial In User Service (RADIUS). IETF RFC 2865, 2000
[124] Garey M. J., Johnson D. S. Computers and intractability: a guide to the theory of NP-Completeness. San Franscisco: Freeman, 1979
[125] Martello S., Pisinger D., Toth P. Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Science, 1999, 45(3): 414 ~ 424
[126] Martello S., Pisinger D., Toth P. New trends in exact algorithms for the 0-1 knapsack problem. European Journal of Operational Research, 2000: 325 ~332
[127] Horowitz E., Sahni S. Computing partitions with applications to the knapsack problem. Journal of ACM, 1974, 21(2): 277~292
[128] Ferreira A. G., A parallel time/hardware tradeoff T.H= O (2 n/2) for the knapsack problem. IEEE Transactions on Computers, 1994, 40(2): 221~225.
[129] Karnin E. D. A parallel algorithm for the knapsack problem. IEEE Transactions on Computers, 1984, 33 (5): 404 ~408
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |