基于网络处理器的流分类系统研究与设计
|
摘要
自因特网兴起以来,其迅猛增长的势头就从未停止,通信链路以吉比特乃至更高的速度进行数据传输己不成问题,而承担网络通讯任务的传统路由器,通常对数据包未加区分尽力而为地转发,这种方式己不能满足网络用户对不同服务的需求。因此路由器需要对数据包进行分类,以提供有差别的网络服务来满足不同的用户需求,流分类技术已成为实现防火墙包过滤、基于策略的路由、虚拟专用网和流量计费等差别服务的基础。由于对每个数据包都要进行分类处理,因此流分类也成为了高速路由器的一个性能瓶颈,如何在可接受的时间和空间复杂度下进行快速的流分类是目前需要解决的一个难题。
基于网络处理器的流分类系统的研究与设计,为高速网络下信息安全的实时检测,促进新一代信息安全检测技术研究的深入,提供了基础。本文对流分类算法进行了研究,以网络处理器为硬件核心,对HiCuts流分类算法进行了改进,将网络处理器技术和并行流分类算法结合起来,研究与设计了一个流分类系统。主要工作包括:
1、在HiCuts算法基础上,提出了改进的HiCuts流分类算法。该算法通过对现有策略库的统计分析,结合HiCuts算法的并行思想,将每次切割的维数变成2维,而且对子空间进行了有效的合并压缩。从而降低了HiCuts算法的空间复杂度,提高了查找速度,同时更适合用网络处理器来实现。
2、以IXP2400为硬件核心,运用改进的HiCuts算法设计和实现了一个高速流分类系统。文章分析了IXP2400的硬件体系架构,基于Intel IXA框架提出了实现流分类系统的软件架构和硬件架构,并给出了软件架构中各功能模块的详细设计及性能分析。同时根据HiCuts算法的并行性要求,对IXP2400的微引擎和存储资源分配作了合理的规划。
3、在算法的实现过程中,针对HiCuts算法实现过程中的数据分配进行了优化,对内存进行压缩,并合理利用网络处理器的任务分配方式。针对IXP2400网络处理器的特点,对流分类算法进行相应的改进,达到了良好的分类效果。
Since the emergence of Intemet, it has kept on developing at an exponentially increasing rate, which currently enables the gigabit or higher transfer speed in the communication networks. However, the traditional router, which offers a Best-of-Service and forwards packets undistinguishedly can't meet the requirement of customized services. And inorder to provide differentiated services for various users, routers should classify packets it receives before forwardlng.Therefore, packet classification has become the foundation of differentiated services such as firewall packet filtering, policy-based routing and so on. However, it has turned out to be a bottleneck of high-speed router, and brings forward the problem of efficient classification with an acceptable time and space complexiy.
This paper research and designs an system of packet classification applying the enhanced HiCuts classifying algorithm. The major work include:
1. Analyzing the statistic status of the rule set, a enhanced algorithm is presented based on the HiCuts algorithm.The new algorithm add the dimension of the cuttings from 1 to 2, and reduce the numbers of child nodes by effective space aggregation method. The new algorithm has a lower space complexity in comparison to HiCuts algorithm, and the search time is much shorter, while it is more practical being carried out on network processor.
2. Applying the new algorithm, a high speed packet classification system is presented based on IXP2400.After analyzing the hardware architecture of IXP2400, we design the software architecture and hardware architecture of an packet classification system under the Intel DCA frame, also giving the detailed design of function blocks. And it also makes a reasonable assignment among the microengines and memory.
3. According to the memory access delay caused by the implement of the HiCuts algorithm, an optimization is presented.After copress the memory and effectively take the advantage of the IXP2400 task assigne method we make significant improvements of the packet classification algorithm,and achieve good results.
基于网络处理器的流分类系统的研究与设计,为高速网络下信息安全的实时检测,促进新一代信息安全检测技术研究的深入,提供了基础。本文对流分类算法进行了研究,以网络处理器为硬件核心,对HiCuts流分类算法进行了改进,将网络处理器技术和并行流分类算法结合起来,研究与设计了一个流分类系统。主要工作包括:
1、在HiCuts算法基础上,提出了改进的HiCuts流分类算法。该算法通过对现有策略库的统计分析,结合HiCuts算法的并行思想,将每次切割的维数变成2维,而且对子空间进行了有效的合并压缩。从而降低了HiCuts算法的空间复杂度,提高了查找速度,同时更适合用网络处理器来实现。
2、以IXP2400为硬件核心,运用改进的HiCuts算法设计和实现了一个高速流分类系统。文章分析了IXP2400的硬件体系架构,基于Intel IXA框架提出了实现流分类系统的软件架构和硬件架构,并给出了软件架构中各功能模块的详细设计及性能分析。同时根据HiCuts算法的并行性要求,对IXP2400的微引擎和存储资源分配作了合理的规划。
3、在算法的实现过程中,针对HiCuts算法实现过程中的数据分配进行了优化,对内存进行压缩,并合理利用网络处理器的任务分配方式。针对IXP2400网络处理器的特点,对流分类算法进行相应的改进,达到了良好的分类效果。
Since the emergence of Intemet, it has kept on developing at an exponentially increasing rate, which currently enables the gigabit or higher transfer speed in the communication networks. However, the traditional router, which offers a Best-of-Service and forwards packets undistinguishedly can't meet the requirement of customized services. And inorder to provide differentiated services for various users, routers should classify packets it receives before forwardlng.Therefore, packet classification has become the foundation of differentiated services such as firewall packet filtering, policy-based routing and so on. However, it has turned out to be a bottleneck of high-speed router, and brings forward the problem of efficient classification with an acceptable time and space complexiy.
This paper research and designs an system of packet classification applying the enhanced HiCuts classifying algorithm. The major work include:
1. Analyzing the statistic status of the rule set, a enhanced algorithm is presented based on the HiCuts algorithm.The new algorithm add the dimension of the cuttings from 1 to 2, and reduce the numbers of child nodes by effective space aggregation method. The new algorithm has a lower space complexity in comparison to HiCuts algorithm, and the search time is much shorter, while it is more practical being carried out on network processor.
2. Applying the new algorithm, a high speed packet classification system is presented based on IXP2400.After analyzing the hardware architecture of IXP2400, we design the software architecture and hardware architecture of an packet classification system under the Intel DCA frame, also giving the detailed design of function blocks. And it also makes a reasonable assignment among the microengines and memory.
3. According to the memory access delay caused by the implement of the HiCuts algorithm, an optimization is presented.After copress the memory and effectively take the advantage of the IXP2400 task assigne method we make significant improvements of the packet classification algorithm,and achieve good results.
引文
[1]方滨兴,建设网络应急体系、保障网络空间安全[J],通信学报,2002,23(5):4-8
[2]Weiss W,Qos with differentiated services[J],Technical Journal,1998,3(4):48-62
[3]Alain Mayer,Avishai Wool,Elisha Ziskind,Fang,A firewall Analysis Engine[J],Proceedings of the 2000 IEEE Symposium on Security and Privacy,May 2000,177-187
[4]Karl Levitt.Intrusion Detection,Current capabilities and Future Directions[J],ACSAC 2002:365-370
[5]Security and VPN[OL],http://www.cisco.corn/en/US/tech/tk583/tsd_technology_support_category _home2005-3-06
[6]Wenke Leesal,Vatore J.Stolfo,A Framework for Constructing Features and Models for Intrusion Detection Systems[J],ACM Transactions on Information and System Security,November 2000,3(4):227-261
[7]3rd Generation Intrusion Detection Technology From Network ICE[OL].http://www.networkice.com,2000
[8]Intel IXP2400 Network Processor Datasheet[R].February 2004
[9]Intel IXP2400 Network Processor Product Brief[R].February 2004
[10]P.Gupta and N.McKeown,Packet classification using hierarchical intelligent cuttings[J],Proc.Hot Interconnects,1999.
[11]M.H.Overmars and A.F.van der Stappen,Range searchingand point location among fat objects[J],Journal of Algorithms,21(3),1996,629-656.
[12]P.Gupta and N.McKeown,Packet classification on multiple fields[J],Proc.ACM SIGCOMM,1999,147-160.
[13]B.Xu,D.Jiang,and J.Li,HSM:A fast packet classification algorithm[C],Proc.19th IEEE International Conference on Advanced Information Networking and Applications(AINA),Taiwan,2005,1:987-992.
[14]V.Srinivasan,G.Varghese,S.Suri and M.Waldvogel,Fast and scalable layer four switching[J],Proc.ACM SIGCOMM,1998,191-202.
[15]F.Baboescu and G.Varghese,Scalable packet classification[J],Proc.ACM SIGCOMM,2001,199-210.
[16]S.Singh,F.Baboescu,G.Varghese and J.Wang,Packet classification using multidimensional cutting[J].Proc.ACMSIGCOMM,2003,213-224.
[17]F.Baboescu,S.Singh and G.Varghese,Packet classification for core routers:Is there an alternative to CAMs[J],Proc.IEEE INFOCOM,2003,1:53-63.
[18]V.Srinivasan,S.Suri and G.Varghese,Packet classification using tuple space search[J],Proc.ACM SIGCOMM,1999,135-146.
[19]J.van Lunteren and T.Engbersen,Fast and scalable packet classification[J],IEEE Journal on Selected Areas in Communications 21(4),2003,560-571.
[20]A.Feldman and S.Muthukrishnan.Tradeoffs for packet classification[J],Proc.IEEE INFOCOM,2000,3:1193-1202.
[21]T.Lakshman and D.Stiliadis,High speed policy-based packet forwarding using efficient multi-dimensional range matching[J],Proc.ACM SIGCOMM,1998,203-214.
[22]T.Y.C Woo,A modular approach to packet classification:algorithms and results[J],Proc.IEEE INFOCOM,2000,3:1213-1222.
[23]F.Geraci,M.Pellegrini and P.Pisati,Packet classification via improved space decomposition Techniques,[J]Proc.IEEE INFOCOM,2005,1:304-312.
[24]Y.Qi and J.Li,Dynamic cuttings:packet classification with network traffic statistics[J],3rd Proc.International Trusted Internet Workshop,2004.
[25]P.Gupta and N.McKewon,Algorithms for packet classification[J],IEEE Network 15(2),2001,24-32.
[26]D.E.Taylor,Survey and taxonomy of packet classification techniques[J],ACM Computing Surveys 37(3),2005,238-275.
[27]M.E.Kounavis,A.Kumar,H.Vin,R.Yavatkar and A.T.Campbell,Directions in packet classification for network processors[J],Proc.2nd Workshop on Network Processors,2003.
[28]Y.Qi,B.Xu and J.Li,Performance evaluation and improvement of algorithmic approaches for packet classification[J],Proc.International Conference on Network and Services,2005.
[29]Yaxuan Qil and Jun Li.Towards Effective Packet Classification[C],Proceedings of the IASTED International Conference Communication,Network,and Information Security October 9-11,2006,MIT,Cambridge,MA,USA
[30]Yaxuan Qil,Bo Xul,Fei Hel,Xin Zhou,Jianming Yu,and Jun Li,Towards Optimized Packet Classification Algorithms for Multi-Core Network Processors[J],International Conference on Parallel Processing
[31]P.Tsuchiya,A Search Algorithm for Table Entries with Non-contiguous Wildcarding[Z],unpublished report,Bellcore.
[32]Xu Ke,Xu Ming—wei,Wu Jian—ping et al.Study of IP classification technology:a survey[J].Mini—Micro Systems,2002,23(7):773—779.
[33]朱秋香,陶军,流分类算法综述[J],小型微型计算机系统,第25卷第10期2004年10月
[34]Intel.IXP2400 and IXP2800 Network Processor:Programmer's Reference Manual U.S.A..Intel Press.January 2005.
[35]Intel.Building Block Apps Design Guide[EB].U.S.A..Intel Press.July 2003.
[36]Intel.Building Blocks Developer's Manual[EB].U.S.A..Intel Press.July 2003.
[37]Intel.IXP2400 Hardware Reference Manual[EB].U.S.A..Intel Press.April 2003.
[38]Intel.Intel XScale Core Developer's Manual[EB].U.S.A..Intel Press.January 2004.
[39]赵艳厂,高速路由器中流分类算法研究与仿真[D],硕士学位论文,北京邮电大学,计算机专业,2000.3.1
[2]Weiss W,Qos with differentiated services[J],Technical Journal,1998,3(4):48-62
[3]Alain Mayer,Avishai Wool,Elisha Ziskind,Fang,A firewall Analysis Engine[J],Proceedings of the 2000 IEEE Symposium on Security and Privacy,May 2000,177-187
[4]Karl Levitt.Intrusion Detection,Current capabilities and Future Directions[J],ACSAC 2002:365-370
[5]Security and VPN[OL],http://www.cisco.corn/en/US/tech/tk583/tsd_technology_support_category _home2005-3-06
[6]Wenke Leesal,Vatore J.Stolfo,A Framework for Constructing Features and Models for Intrusion Detection Systems[J],ACM Transactions on Information and System Security,November 2000,3(4):227-261
[7]3rd Generation Intrusion Detection Technology From Network ICE[OL].http://www.networkice.com,2000
[8]Intel IXP2400 Network Processor Datasheet[R].February 2004
[9]Intel IXP2400 Network Processor Product Brief[R].February 2004
[10]P.Gupta and N.McKeown,Packet classification using hierarchical intelligent cuttings[J],Proc.Hot Interconnects,1999.
[11]M.H.Overmars and A.F.van der Stappen,Range searchingand point location among fat objects[J],Journal of Algorithms,21(3),1996,629-656.
[12]P.Gupta and N.McKeown,Packet classification on multiple fields[J],Proc.ACM SIGCOMM,1999,147-160.
[13]B.Xu,D.Jiang,and J.Li,HSM:A fast packet classification algorithm[C],Proc.19th IEEE International Conference on Advanced Information Networking and Applications(AINA),Taiwan,2005,1:987-992.
[14]V.Srinivasan,G.Varghese,S.Suri and M.Waldvogel,Fast and scalable layer four switching[J],Proc.ACM SIGCOMM,1998,191-202.
[15]F.Baboescu and G.Varghese,Scalable packet classification[J],Proc.ACM SIGCOMM,2001,199-210.
[16]S.Singh,F.Baboescu,G.Varghese and J.Wang,Packet classification using multidimensional cutting[J].Proc.ACMSIGCOMM,2003,213-224.
[17]F.Baboescu,S.Singh and G.Varghese,Packet classification for core routers:Is there an alternative to CAMs[J],Proc.IEEE INFOCOM,2003,1:53-63.
[18]V.Srinivasan,S.Suri and G.Varghese,Packet classification using tuple space search[J],Proc.ACM SIGCOMM,1999,135-146.
[19]J.van Lunteren and T.Engbersen,Fast and scalable packet classification[J],IEEE Journal on Selected Areas in Communications 21(4),2003,560-571.
[20]A.Feldman and S.Muthukrishnan.Tradeoffs for packet classification[J],Proc.IEEE INFOCOM,2000,3:1193-1202.
[21]T.Lakshman and D.Stiliadis,High speed policy-based packet forwarding using efficient multi-dimensional range matching[J],Proc.ACM SIGCOMM,1998,203-214.
[22]T.Y.C Woo,A modular approach to packet classification:algorithms and results[J],Proc.IEEE INFOCOM,2000,3:1213-1222.
[23]F.Geraci,M.Pellegrini and P.Pisati,Packet classification via improved space decomposition Techniques,[J]Proc.IEEE INFOCOM,2005,1:304-312.
[24]Y.Qi and J.Li,Dynamic cuttings:packet classification with network traffic statistics[J],3rd Proc.International Trusted Internet Workshop,2004.
[25]P.Gupta and N.McKewon,Algorithms for packet classification[J],IEEE Network 15(2),2001,24-32.
[26]D.E.Taylor,Survey and taxonomy of packet classification techniques[J],ACM Computing Surveys 37(3),2005,238-275.
[27]M.E.Kounavis,A.Kumar,H.Vin,R.Yavatkar and A.T.Campbell,Directions in packet classification for network processors[J],Proc.2nd Workshop on Network Processors,2003.
[28]Y.Qi,B.Xu and J.Li,Performance evaluation and improvement of algorithmic approaches for packet classification[J],Proc.International Conference on Network and Services,2005.
[29]Yaxuan Qil and Jun Li.Towards Effective Packet Classification[C],Proceedings of the IASTED International Conference Communication,Network,and Information Security October 9-11,2006,MIT,Cambridge,MA,USA
[30]Yaxuan Qil,Bo Xul,Fei Hel,Xin Zhou,Jianming Yu,and Jun Li,Towards Optimized Packet Classification Algorithms for Multi-Core Network Processors[J],International Conference on Parallel Processing
[31]P.Tsuchiya,A Search Algorithm for Table Entries with Non-contiguous Wildcarding[Z],unpublished report,Bellcore.
[32]Xu Ke,Xu Ming—wei,Wu Jian—ping et al.Study of IP classification technology:a survey[J].Mini—Micro Systems,2002,23(7):773—779.
[33]朱秋香,陶军,流分类算法综述[J],小型微型计算机系统,第25卷第10期2004年10月
[34]Intel.IXP2400 and IXP2800 Network Processor:Programmer's Reference Manual U.S.A..Intel Press.January 2005.
[35]Intel.Building Block Apps Design Guide[EB].U.S.A..Intel Press.July 2003.
[36]Intel.Building Blocks Developer's Manual[EB].U.S.A..Intel Press.July 2003.
[37]Intel.IXP2400 Hardware Reference Manual[EB].U.S.A..Intel Press.April 2003.
[38]Intel.Intel XScale Core Developer's Manual[EB].U.S.A..Intel Press.January 2004.
[39]赵艳厂,高速路由器中流分类算法研究与仿真[D],硕士学位论文,北京邮电大学,计算机专业,2000.3.1