IP骨干链路流量测量技术研究
|
摘要
网络测量是对网络行为进行特征化、对各项指标进行量化并充分理解与正确认识互联网的最基本的手段。在骨干链路中，数据处理面临的最大问题是高速带宽带来的处理压力和由此产生的庞大的数据集。因此，为了处理庞大的数据集，抽样是一种重要的数据缩减方式。通过将抽样技术应用于网络数据，然后由抽样所得的数据生成支持常规查询和统计的概要信息，是对高速网络流量有效测量的一个很好的解决方案。
论文结合国家863计划重大专项“新一代高可信网络”的研究，从高速网络环境下流量测量的可操作性、可扩展性的应用需求出发，针对现有高速骨干链路中流量测量技术存在的问题，对骨干链路中高速网络数据的抽样技术和基于计数型布鲁姆过滤器的概要表示方法进行了研究，并设计了骨干链路流量测量系统架构，为骨干链路流量测量构建了一种有效的解决方案。本文主要工作如下：夺针对NetFlow静态抽样概率在网络流量变化时不够灵活的缺陷，提出了一种基于包速
率自适应的报文抽样算法。通过测量包速率，采用预设测量误差的方法，根据包速率的变化自适应调整抽样概率，从而达到在有限资源情况下控制测量误差的目的。基于实际互联网数据进行了仿真试验，结果显示：与传统的Netflowr算法相比，该方法易于实现，测量误差可控，具有高效性，不失准确性，并有效节约处理资源。
夺针对计数型布鲁姆过滤器存储数据时受计数器溢出的限制，提出了一种基于分层计数型布鲁姆过滤器(Hierarchy counl，。mg Bloom Filter HcBF)的概要数据结构及算法。该算法给出了一个严格的计数溢出门限，基于该门限将计数型布鲁姆过滤器fcountmg Bloom Filter，cBFl结构扩展到多层，并能自适应的配置各层计数型布鲁姆过滤器参数，将测量误差控制在预定范围内。仿真结果表明，与cBF相比，在同样溢出概率条件下，该结构节省了大量的内存资源。
夺针对骨干链路中流量测量面临的可扩展性挑战，设计了骨干链路网络流量实时管理系统的实现方案。该方案设计了骨干网实时流量管理前端抽样和后端统计的系统实现方法，并对系统的性能进行了仿真，结果表明，该系统能够有效的识别网络中的大流量对象。
Traffic Measurement lS the most basic method of characterizing network behavior,estimating the performances，and absolutely understanding and recognizing the network But inthe IP backbone links，the biggest challenge of data processing is the pressure of the data fromthe high speed network and the enormous data volume caused by this process Sampling is animportant method for data decrease Network sampling data,can be used to form summaryinformation，which could support general querying and statistic And this is an effectiveresolution for the backbone traffiC measurement
Combined with the research and development ofthe key technologies for“New-GenerationNetwork with High Trustability”，to meet the need of operable and scalable application in highspeed networks，this dissertation，which aims to resolved the problem of the currentmeasurement technology,analyzes the sampling algorithm，studies the summary denotationmethod which is basic on Counting Bloom Filter,and designs a new-structure for traAl]cmeasurement which iS a suitahle resolution for IP backbone Its main W'Ork and COntributions areOutlinedasfollows：
_As the inflexibility ofNetFlow’S sampling probability,the packet sampling algorithm．based on adaptive packet rate，is proposed This algorithm measures the packet rate，predefmes the measurement error,and adaptively adjusts the sampling probability according to the packet rate，SO as to control the measurement error under the condition of limited resources Experiments are conducted based on real network traces Results demonstrate that the proposed method is easy to be implemented，with controllable measurement error,higher efficiency and accurac~while memory consumption is lower compared with other methods
_To conquer the overflow-limitation of memory structure in Counting Bloom Fiker,a novel mechanism based on Hieraacchy Counting Bloom Fiker(HCBF)for large flow-inspect is proposed This algorithm defines a strict threshold of counting overflow-,and extends the standard structure of Counting Bloom Filter(CBF)to multi-layer The mechanism can not only adjust the configurable parameter,but also control the measurement error to a limited scale Results demonstrate that the proposed mechanism can save enormous space，under the same overflow-probability．
_To meet the scalable challenge of backbone traffic measurement．this paper designs the real-time measurement management system structure Based on this structure，this paper summarizes the implement method of sampling for front end and statistic for back end，and simulates the performance of the system and the result shows that：it is effective for large t]0w in the network
论文结合国家863计划重大专项“新一代高可信网络”的研究，从高速网络环境下流量测量的可操作性、可扩展性的应用需求出发，针对现有高速骨干链路中流量测量技术存在的问题，对骨干链路中高速网络数据的抽样技术和基于计数型布鲁姆过滤器的概要表示方法进行了研究，并设计了骨干链路流量测量系统架构，为骨干链路流量测量构建了一种有效的解决方案。本文主要工作如下：夺针对NetFlow静态抽样概率在网络流量变化时不够灵活的缺陷，提出了一种基于包速
率自适应的报文抽样算法。通过测量包速率，采用预设测量误差的方法，根据包速率的变化自适应调整抽样概率，从而达到在有限资源情况下控制测量误差的目的。基于实际互联网数据进行了仿真试验，结果显示：与传统的Netflowr算法相比，该方法易于实现，测量误差可控，具有高效性，不失准确性，并有效节约处理资源。
夺针对计数型布鲁姆过滤器存储数据时受计数器溢出的限制，提出了一种基于分层计数型布鲁姆过滤器(Hierarchy counl，。mg Bloom Filter HcBF)的概要数据结构及算法。该算法给出了一个严格的计数溢出门限，基于该门限将计数型布鲁姆过滤器fcountmg Bloom Filter，cBFl结构扩展到多层，并能自适应的配置各层计数型布鲁姆过滤器参数，将测量误差控制在预定范围内。仿真结果表明，与cBF相比，在同样溢出概率条件下，该结构节省了大量的内存资源。
夺针对骨干链路中流量测量面临的可扩展性挑战，设计了骨干链路网络流量实时管理系统的实现方案。该方案设计了骨干网实时流量管理前端抽样和后端统计的系统实现方法，并对系统的性能进行了仿真，结果表明，该系统能够有效的识别网络中的大流量对象。
Traffic Measurement lS the most basic method of characterizing network behavior,estimating the performances，and absolutely understanding and recognizing the network But inthe IP backbone links，the biggest challenge of data processing is the pressure of the data fromthe high speed network and the enormous data volume caused by this process Sampling is animportant method for data decrease Network sampling data,can be used to form summaryinformation，which could support general querying and statistic And this is an effectiveresolution for the backbone traffiC measurement
Combined with the research and development ofthe key technologies for“New-GenerationNetwork with High Trustability”，to meet the need of operable and scalable application in highspeed networks，this dissertation，which aims to resolved the problem of the currentmeasurement technology,analyzes the sampling algorithm，studies the summary denotationmethod which is basic on Counting Bloom Filter,and designs a new-structure for traAl]cmeasurement which iS a suitahle resolution for IP backbone Its main W'Ork and COntributions areOutlinedasfollows：
_As the inflexibility ofNetFlow’S sampling probability,the packet sampling algorithm．based on adaptive packet rate，is proposed This algorithm measures the packet rate，predefmes the measurement error,and adaptively adjusts the sampling probability according to the packet rate，SO as to control the measurement error under the condition of limited resources Experiments are conducted based on real network traces Results demonstrate that the proposed method is easy to be implemented，with controllable measurement error,higher efficiency and accurac~while memory consumption is lower compared with other methods
_To conquer the overflow-limitation of memory structure in Counting Bloom Fiker,a novel mechanism based on Hieraacchy Counting Bloom Fiker(HCBF)for large flow-inspect is proposed This algorithm defines a strict threshold of counting overflow-,and extends the standard structure of Counting Bloom Filter(CBF)to multi-layer The mechanism can not only adjust the configurable parameter,but also control the measurement error to a limited scale Results demonstrate that the proposed mechanism can save enormous space，under the same overflow-probability．
_To meet the scalable challenge of backbone traffic measurement．this paper designs the real-time measurement management system structure Based on this structure，this paper summarizes the implement method of sampling for front end and statistic for back end，and simulates the performance of the system and the result shows that：it is effective for large t]0w in the network
引文
[1]中国互联网络信息中心中国互联网络发展状况统计报告[EB／OL]．http：／／www cnnic cn／index／0E／00／1i／indexhtml 2010-2
[2] SNMP[EB／OL]．http：／／www．cisco com／univercd／cc／td／doc／cisintwk／ito doc／snmp html 2009．11
[3] RMON[EB／OL]．http：／／www cisco com／univercd／cc／td／doc／cisintwk／ito doc／rmon html 2009．11
[4] Cisco System NetFlow Services Solutions Guide[EB／OL]http：／／www．cisco com／en／US／docs／ios／solutions docs／netflow／nfwhite html，2009-10
[5] Random Sampled Netflow[EB／OL]http：／／www cisco com／en／US／products／sw／iosswrel／ps5207／t)roducts feature guide09186a0080la7618 html 2009-10
[6]杨家海，吴建平，安常青互联网络测量理论与应用[M]北京：人民邮电出版社，2009：48．49
[7] Fralergh C，Doit C，Lvles B，et al Design and deployment of a passive monitoring infrastructure[C]In Proceedings of the Thyrrhenian International Workshop on Digital Communications：Evolutionary Trends ofthe Internet，200 1
[8]周明中大规模网络IP流行为特性及其测量算法研究[D]南京：东南大学博士学位论文．2006
[9] A1Tler~ED，Cassel，L N Management of Sampled Real-time Network Measurements[C] In：Proceedings 14th Conference on Local Computer Networks，Mineapolis，MN，USA，1989：62．68
[10]K C Claffy,George C Polyzos，Hams Werner Braun Application of sampling methodologies to network traffic chaxacterization[C]In：Proc of ACM Sigcomm，Madison，1993，267-280
[11]Estan C，Varghese G New-directions in traffic measurement and accounting：Focusing on elephants，ignoring the mice[J]ACM Transaction on Computer Systems，2003，21(3)：270．313
[12]Abhishek Kumar,Jun(Jim)Xu Sketch Guided Sampling Using On-Line Estimates of Flow-Size for Adaptive Data Collection[C]In：Proc of IEEE Infocom’06，Barcelona，2005，467-482
[13]Fralergh C，Doit C，Lyles B，et al Design and deployment of a passive monitoring infrastructure[C]In Proceedings of the Thyrrhenian International Workshop on Digital Communications：Evolutionary Trends ofthe Internet，200 1
[14]A Broder,M MRzenmacher．Network applications of bloom filters：A survey[C]In：Proc ofAlle~on Conference，2002
[15]F Bonomi，M Mitzenmacher,R Pamigrahy,S Singh，G Varghese Beyond Bloom Fikers：From Approximate Membership Checks to Approximate State Machines[C] In：Proceedings ofACM SIGCOMM，Providence，2006：342。356
[16]Abhishek Kumar Jun(Jim)Xu Space-Code Bloom Filter for Efficient Per-Flow-Traffic Measurement[C]In：Proc of IEEE Infocom’04，HongKong，2004，3 1 5-328
[17]Cypress SRAM[EB／OL]http：／／www cypress com／products／?gid。5&fid。39&Go GatewayCategorylD。All&2010-2
[18]M Mitzenmacher Compressed bloom fikers[C]In PODC’01：Proc of the twentieth annual ACM symposium on Principles of distributedcomputing New-York，NY USA：ACM Press，2001，144-150
[19]Saaac Cohen，Yossi Matias Spectral Bloom Filters[C]Proceedings of the 2003 ACM SIGMOD Intemational Conference on Management of Data，San Diego California，2003：241-252
[20]F Bonomi，M M~zenmacher,R Panigrahy,S Singh，G Vaxghese An Improved Construction for Counting Bloom Filters[C]European Symposium on Algorithms，SydneG 2006．678．680[2 1]Cristian Estan，Ken Keys，David Moore，George Varghese Building a Better NetFlow[C] In Proc ofACM Sigcomm，Hague，2006，432-445
[22]Wang HB，Wei AM，Lin Y Cheng SD Time stratified packet sampling based on measurement buffer for flow-measurement[J]Journal ofSoftware，2006，17(8)：1775-1784 (in Chinese with English abstract)
[23]盛聚，谢式千，潘承毅概率论与数理统计[M]北京：高等教育出版社，2001：104．142
[24]杜子芳抽样技术及其应用[M]北京：清华大学出版社，2005：124-132
[25]NLANR[EB／0L]．http：／／pmanlanr,net／Traces／Traces／daily／20050801，2008-12
[26]IDT．SRAMs[EB／OL]http：／／www idt com／?catID。58743&source。memory app 2009-8
[27]Samsung HighSpeedSRAM[EB／OL]http：／／www．samsung com2global／business／semicond- uctor／products／sram／Products HighSpeedSRAM html 2009-5
[28]Xie K，Min Y H，Zhang D E Xie G G Wen J G Basket Bloom filter for membership queries[J]Chinese Journal ofComputers，2007，4(30)：597-607
[29]Sun Yong，Zhang Zhibin，Guo Li，Bai Shuo，Tan Jianlong An effective algorithm for counting active flow-s based on loop filter[C]Proc Intemational Conference on Networking，Architecture，and Storage，IEEE Computer Society,Chongqing China，2008：104．109
[30]Gong J，Peng Y B，Yang W and Liu W J Reconstructing the parameter for massive abnormal TCP connection with Bloom filter[J]Journal of Software，2006，17(3)：434-444[3 1]B Bloom Space／Time Trade-offs in Hash Coding with Allowable Errors[C] Communication ofthe ACM，13(7)，1970：422-426
[32]同济大学数学教研室高等数学(第四版)[M]北京：高等教育出版社，2000：124-132
[33]F Bonomi，M Mitzenmacher,R Panigrahy,S Singh，G Varghese Beyond Bloom filters：From approximate membership checks to approximate state machines[C]In：Proc of ACM SIGCOMM，Providence，2006，342-356
[34]A Smitha，Inkoo kim，A L N ReddN Identifying long-term high bandwidth flow-s at a router[C]In Proceeding of High Performance Compming，200 1
[35]XIE K，MIN Y H，ZHANG D E et al A Scalable Bloom Filter for Membership Queries[C] Proc of IEEE Globlecom Washington D C US A．2007
[36]XILINX Virtex-4 Pro and Virtex-4 Pro X Complete Data Sheet[EB／OL] http：／／www XILINX com，2009-03
[37]F Yu，R Katz，T V Lakshman Gigabit Rate Packet Pattern-matching Using TCAM[C]In IEEE Intemational Conference on Network Protocols(ICNP)，Berlin，2004，174-183
[38]刘昭，苏厉，金德鹏，陈虹等．10G以太网系统中的并行CRC编解码器的设计[LIl_电子技术应用，2004，30(4)：70．72
[39]程光，龚俭，丁伟，徐加羚面向IP流测量的哈希算法研究[J1．软件学报，2005，16(5)：56．64
[40]束礼宝，宋克柱，王砚方．伪随机数发生器的FPGA实现与研究[J1．电路与系统学报2003，8(3)：121．124．
[41]张进．基于布鲁姆过滤器的IP骨干网流量分析前端处理算法研究[D]．郑州：解放军信息工程大学博士学位论文．2008
[2] SNMP[EB／OL]．http：／／www．cisco com／univercd／cc／td／doc／cisintwk／ito doc／snmp html 2009．11
[3] RMON[EB／OL]．http：／／www cisco com／univercd／cc／td／doc／cisintwk／ito doc／rmon html 2009．11
[4] Cisco System NetFlow Services Solutions Guide[EB／OL]http：／／www．cisco com／en／US／docs／ios／solutions docs／netflow／nfwhite html，2009-10
[5] Random Sampled Netflow[EB／OL]http：／／www cisco com／en／US／products／sw／iosswrel／ps5207／t)roducts feature guide09186a0080la7618 html 2009-10
[6]杨家海，吴建平，安常青互联网络测量理论与应用[M]北京：人民邮电出版社，2009：48．49
[7] Fralergh C，Doit C，Lvles B，et al Design and deployment of a passive monitoring infrastructure[C]In Proceedings of the Thyrrhenian International Workshop on Digital Communications：Evolutionary Trends ofthe Internet，200 1
[8]周明中大规模网络IP流行为特性及其测量算法研究[D]南京：东南大学博士学位论文．2006
[9] A1Tler~ED，Cassel，L N Management of Sampled Real-time Network Measurements[C] In：Proceedings 14th Conference on Local Computer Networks，Mineapolis，MN，USA，1989：62．68
[10]K C Claffy,George C Polyzos，Hams Werner Braun Application of sampling methodologies to network traffic chaxacterization[C]In：Proc of ACM Sigcomm，Madison，1993，267-280
[11]Estan C，Varghese G New-directions in traffic measurement and accounting：Focusing on elephants，ignoring the mice[J]ACM Transaction on Computer Systems，2003，21(3)：270．313
[12]Abhishek Kumar,Jun(Jim)Xu Sketch Guided Sampling Using On-Line Estimates of Flow-Size for Adaptive Data Collection[C]In：Proc of IEEE Infocom’06，Barcelona，2005，467-482
[13]Fralergh C，Doit C，Lyles B，et al Design and deployment of a passive monitoring infrastructure[C]In Proceedings of the Thyrrhenian International Workshop on Digital Communications：Evolutionary Trends ofthe Internet，200 1
[14]A Broder,M MRzenmacher．Network applications of bloom filters：A survey[C]In：Proc ofAlle~on Conference，2002
[15]F Bonomi，M Mitzenmacher,R Pamigrahy,S Singh，G Varghese Beyond Bloom Fikers：From Approximate Membership Checks to Approximate State Machines[C] In：Proceedings ofACM SIGCOMM，Providence，2006：342。356
[16]Abhishek Kumar Jun(Jim)Xu Space-Code Bloom Filter for Efficient Per-Flow-Traffic Measurement[C]In：Proc of IEEE Infocom’04，HongKong，2004，3 1 5-328
[17]Cypress SRAM[EB／OL]http：／／www cypress com／products／?gid。5&fid。39&Go GatewayCategorylD。All&2010-2
[18]M Mitzenmacher Compressed bloom fikers[C]In PODC’01：Proc of the twentieth annual ACM symposium on Principles of distributedcomputing New-York，NY USA：ACM Press，2001，144-150
[19]Saaac Cohen，Yossi Matias Spectral Bloom Filters[C]Proceedings of the 2003 ACM SIGMOD Intemational Conference on Management of Data，San Diego California，2003：241-252
[20]F Bonomi，M M~zenmacher,R Panigrahy,S Singh，G Vaxghese An Improved Construction for Counting Bloom Filters[C]European Symposium on Algorithms，SydneG 2006．678．680[2 1]Cristian Estan，Ken Keys，David Moore，George Varghese Building a Better NetFlow[C] In Proc ofACM Sigcomm，Hague，2006，432-445
[22]Wang HB，Wei AM，Lin Y Cheng SD Time stratified packet sampling based on measurement buffer for flow-measurement[J]Journal ofSoftware，2006，17(8)：1775-1784 (in Chinese with English abstract)
[23]盛聚，谢式千，潘承毅概率论与数理统计[M]北京：高等教育出版社，2001：104．142
[24]杜子芳抽样技术及其应用[M]北京：清华大学出版社，2005：124-132
[25]NLANR[EB／0L]．http：／／pmanlanr,net／Traces／Traces／daily／20050801，2008-12
[26]IDT．SRAMs[EB／OL]http：／／www idt com／?catID。58743&source。memory app 2009-8
[27]Samsung HighSpeedSRAM[EB／OL]http：／／www．samsung com2global／business／semicond- uctor／products／sram／Products HighSpeedSRAM html 2009-5
[28]Xie K，Min Y H，Zhang D E Xie G G Wen J G Basket Bloom filter for membership queries[J]Chinese Journal ofComputers，2007，4(30)：597-607
[29]Sun Yong，Zhang Zhibin，Guo Li，Bai Shuo，Tan Jianlong An effective algorithm for counting active flow-s based on loop filter[C]Proc Intemational Conference on Networking，Architecture，and Storage，IEEE Computer Society,Chongqing China，2008：104．109
[30]Gong J，Peng Y B，Yang W and Liu W J Reconstructing the parameter for massive abnormal TCP connection with Bloom filter[J]Journal of Software，2006，17(3)：434-444[3 1]B Bloom Space／Time Trade-offs in Hash Coding with Allowable Errors[C] Communication ofthe ACM，13(7)，1970：422-426
[32]同济大学数学教研室高等数学(第四版)[M]北京：高等教育出版社，2000：124-132
[33]F Bonomi，M Mitzenmacher,R Panigrahy,S Singh，G Varghese Beyond Bloom filters：From approximate membership checks to approximate state machines[C]In：Proc of ACM SIGCOMM，Providence，2006，342-356
[34]A Smitha，Inkoo kim，A L N ReddN Identifying long-term high bandwidth flow-s at a router[C]In Proceeding of High Performance Compming，200 1
[35]XIE K，MIN Y H，ZHANG D E et al A Scalable Bloom Filter for Membership Queries[C] Proc of IEEE Globlecom Washington D C US A．2007
[36]XILINX Virtex-4 Pro and Virtex-4 Pro X Complete Data Sheet[EB／OL] http：／／www XILINX com，2009-03
[37]F Yu，R Katz，T V Lakshman Gigabit Rate Packet Pattern-matching Using TCAM[C]In IEEE Intemational Conference on Network Protocols(ICNP)，Berlin，2004，174-183
[38]刘昭，苏厉，金德鹏，陈虹等．10G以太网系统中的并行CRC编解码器的设计[LIl_电子技术应用，2004，30(4)：70．72
[39]程光，龚俭，丁伟，徐加羚面向IP流测量的哈希算法研究[J1．软件学报，2005，16(5)：56．64
[40]束礼宝，宋克柱，王砚方．伪随机数发生器的FPGA实现与研究[J1．电路与系统学报2003，8(3)：121．124．
[41]张进．基于布鲁姆过滤器的IP骨干网流量分析前端处理算法研究[D]．郑州：解放军信息工程大学博士学位论文．2008