低速率流淘汰与d- Left散列相结合的大流检测算法
|
摘要
网络中少量较高速率和较大数据量的流生成了网络的大部分流量;利用有限的存储空间有效地识别出这些数据流,对实施流量工程、缓解网络拥塞、改善网络传输具有非常重要的意义.随着网络技术的发展,传输链路的带宽容量和数据流的传输速率越来越高.具有高速报文转发能力的网络设备对数据流检测算法的处理提出了高的性能要求.将超过一定的数据量和传输速率的数据流定义为大流,提出了将低速流淘汰与d-Left散列表存储结构相结合的大流检测算法.为了满足高速网络传输的性能需求,使用d-Left散列表存储流检测的数据结构,将d-Left散列表的存储结构与流缓存替换相结合以实现高效的大流检测.通过低速率的淘汰,提高了检测算法的准确性.基于真实网络数据的测试结果表明:所提算法在相近的存储开销下保持了高的处理性能,其准确性优于LRU派生算法S-LRU和L-LRU以及CSS和WCSS检测算法.
A small percentage of high rate large-sized flows consume most of the network bandwidth. It is of great significance to efficiently identify these flows for traffic engineering, so as to alleviate network congestion and improve network transport performance. With the development of network technology, the capacity of transmission links and the transfer rate of data flows become higher and higher. So the network equipment with high-speed packets forwarding capability put forward high performance requirements for flows identifying algorithms. The flows whose size and transmission rate both exceed certain thresholds are usually defined as elephant flows. In this paper, a novel algorithm is proposed for elephant flow detection, in which the data structure of flow entries is indexed by d-Left Hash table to meet the performance requirements of high speed packet processing. The proposed detection algorithm combines the d-Left Hash data structure with the eviction of low-rate flows' entries in order to identify elephant flows efficiently. The accuracy of the proposed detection algorithm is improved by the eviction of low rate flows' entries. Theoretical analysis is conducted to demonstrate the accuracy, performance and memory overhead of the proposed detection algorithm. Experimental results on real data sets show that the proposed algorithm outperforms CSS, WCSS, S-LRU and L-LRU algorithms in terms of accuracy and performance at comparable memory overhead.
A small percentage of high rate large-sized flows consume most of the network bandwidth. It is of great significance to efficiently identify these flows for traffic engineering, so as to alleviate network congestion and improve network transport performance. With the development of network technology, the capacity of transmission links and the transfer rate of data flows become higher and higher. So the network equipment with high-speed packets forwarding capability put forward high performance requirements for flows identifying algorithms. The flows whose size and transmission rate both exceed certain thresholds are usually defined as elephant flows. In this paper, a novel algorithm is proposed for elephant flow detection, in which the data structure of flow entries is indexed by d-Left Hash table to meet the performance requirements of high speed packet processing. The proposed detection algorithm combines the d-Left Hash data structure with the eviction of low-rate flows' entries in order to identify elephant flows efficiently. The accuracy of the proposed detection algorithm is improved by the eviction of low rate flows' entries. Theoretical analysis is conducted to demonstrate the accuracy, performance and memory overhead of the proposed detection algorithm. Experimental results on real data sets show that the proposed algorithm outperforms CSS, WCSS, S-LRU and L-LRU algorithms in terms of accuracy and performance at comparable memory overhead.
引文
[1]Zhang Yin,Breslau L,Paxson V,et al.On the characteristics and origins of Internet flow rates[C]Proc of ACM SIGCOMM’02.New York:ACM,2002:309-322
[2]Benson T,Akella A,Maltz D A.Network traffic characteristics of data centers in the wild[C]Proc of the10th ACM SIGCOMM Conf on Internet Measurement.New York:ACM,2010:267-280
[3]Roy A,Zeng Hongyi,Bagga J,et al.Inside the social network’s(datacenter)network[J].ACM SIGCOMMComputer Communication Review,2015,45(4):123-137
[4]Mahajan R,Floyd S,Wetherall D.Controlling highbandwidth flows at the congested router[C]Proc of the 9th Int Conf on Network Protocols(ICNP).Piscataway,NJ:IEEE,2001:192-201
[5]Smitha,Kim I,Reddy A.Identifying long-term high bandwidth flows at a router[C]Proc of the 8th Int Conf on High Performance Computing.Piscataway,NJ:IEEE,2001:361-371
[6]Guo Liang,Matta I.The war between mice and elephants[C]Proc of the 9th Int Conf on Network Protocols(ICNP).Piscataway,NJ:IEEE,2001:180-188
[7]Alizadeh M,Greenberg A,Maltz D A,et al.Data center TCP(dcTCP)[J].ACM SIGCOMM Computer Communication Review,2010,40(4):63-74
[8]Fred B,Gorry F.IETF recommendations regarding active queue management,RFC 7567[S/OL].2015[2017-05-09].http:www.rfc-editor.org/info/rfc7567
[9]Papagiannakit K,Taft N,Diot C.Impact of flow dynamics on traffic engineering design principles[C]Proc of the 23rd IEEE INFOCOM.New York:IEEE Communications Society,2004:2295-2306
[10]Cui Weizhi,Ye Yu,Chen Qian.DiFS:Distributed flow scheduling for adaptive switching in Fat Tree data center networks[J].Computer Networks,2016:166-179
[11]Agarwal S,Kodialam M,Lakshman T V.Traffic engineering in software defined networks[C]Proc of the32nd IEEE INFOCOM.New York:IEEE Communications Society,2013:2211-2219
[12]Long Le,Aikat J,Jeffay K,et al.Differential congestion notification:Taming the elephants[C]Proc of the 12th IEEE Int Conf on Network Protocols.Piscataway,NJ:IEEE,2004:118-128
[13]Voorhies S,Lee H,Klappenecker A.Fair service for mice in the presence of elephants[J].Information Processing Letters,2006,99(3):96-101
[14]Estan C,Varghese G.New directions in traffic measurement and accounting:Focusing on the elephants,ignoring the mice[J].ACM Transactions on Computer Systems,2003,21(3):270-313
[15]Cisco Systems Incorporation.Cisco nexus 9500 platform common equipment data sheet[EB/OL].(2016-05-29)[2017-03-21].http:www.cisco.com/c/en/us/products/collateral/switches/nexus-9000-series-switches/datasheet-c78-729404.html
[16]Huawei Technology Incorporation.NetEngine5000Ecluster routers[EB/OL].[2017-04-25].http:e.huawei.com/en/products/enterprise-networking/routers/ne/ne5000e
[17]V9cking B.How asymmetry helps load balancing[J].Journal of the ACM,2003,50(4):568-589
[18]Che Lichang,Qiu Bin,Wu Hongren.Improvement of LRUcache for the detection and control of long-lived high bandwidth flows[J].Computer Communication,2005,29(1):103-113
[19]Choi Y,Joung J.A novel algorithm for detection of elephant flows:Landmark-LRU with recycle[G]Future Information Communication Technology and Applications.Berlin:Springer,2013:159-167
[20]Ben-Basat R,Einziger G,Friedman R,et al.Heavy hitters in streams and sliding windows[C]Proc of the 35th IEEEINFOCOM.New York:IEEE Communications Society,2016:1-9
[21]WIDE MAWI Working Group.MAWI working group traffic archive[OL].[2017-07-22].http:mawi.wide.ad.jp/mawi/
[22]Waikato WAND Network Research Group.Waikato Internet traffic storage[OL].[2017-01-12].http:wand.net.nz/wits/waikato/8/20110606-000000-0.php
[23]Benson T.Data set for IMC 2010data center measurement[OL].[2016-11-12].http:pages.cs.wisc.edu/~tbenson/IMC10_Data.html
[24]Cormode G,Muthukrishnan S.An improved data stream summary:The count-min sketch and its applications[J].Journal of Algorithms,2005,55(1):58-75
[25]Bai Lei,Chen Chao.Frequent items mining algorithm over high speed network flows based on double hash method[J].International Journal of Future Generation Communication and Networking,2016,9(5):75-82
[26]Chen Ling,Mei Qingling.Mining frequent items in data stream using time fading model[J].Information Sciences,2014,257:54-69
[27]Cafaroa M,Pulimenoa M,Epicocoa I,et al.Mining frequent items in the time fading model[J].Information Sciences,2016,(370/371):221-238
[28]Manku G,Motwani R.Approximate frequency counts over data streams[C]Proc of the 28th Int Conf on Very Large Databases.New York:ACM,2002:346-357
[29]Dimitropoulos X,Hurley P,Kind A.Probabilistic lossy counting:An efficient algorithm for finding heavy hitters[J].ACM SIGCOMM Computer Communication Review,2008,38(1):5-15
[30]Zhang Yu,Fang Binxing,Zhang Yongzheng.Identifying heavy hitters in high-speed network monitoring[J].Science China Information Sciences,2010,40(2):340-355(in Chinese)(张玉,方滨兴,张永铮.高速网络监控中大流量对象的识别[J].中国科学:信息科学,2010,40(2):340-355)
[31]Basat R B,Einziger G,Friedman R,et al.Optimal elephant flow detection[C]Proc of the 36th Annual IEEE Int Conf on Computer Communication.New York:IEEE Communications Society,2017:1-9
[32]Metwally A,Agrawal D,El Abbadi A.Efficient computation of frequent and top-k elements in data streams[C]Proc of the 10th Int Conf on Database Theory.Berlin:Springer,2005:398-412
[33]Carvalho P,Lima S R.Analyzing traffic flows through sampling:A comparative study[C]Proc of the 20th IEEESymp on Computers and Communication(ISCC).Piscataway,NJ:IEEE,2015:341-346
[34]Mori T,Uchida M,Kawahara R,et al.Identifying elephant flows through periodically sampled packets[C]Proc of the4th ACM SIGCOMM Conf on Internet Measurement.New York:ACM,2004:115-120
[35]Arasu A,Manku G S.Approximate counts and quantiles over sliding windows[C]Proc of the 23rd ACM SIGMOD-SIGACT-SIGART Symp on Principles of Database Systems.New York:ACM,2004:286-296
[36]Zhu Rui,Wang Bin,Luo Shiying,et al.Approximate continuous top-k query over sliding window[J].Journal of Computer Science and Technology,2017,32(1):93-109
[37]Kudo T,Takine T.Design of a sliding window scheme for detecting high packet-rate flows via random packet sampling[J].Computer Networks,2011,55(6):1351-1363
[38]Bai Lei,Tian Liqin,Chen Chao.A TCBF-LRU algorithm for identifying and measuring elephant flows in high speed network[J].Journal of Computer Research and Development,2014,51(1):122-128(in Chinese)(白磊,田立勤,陈超.基于TCBF-LRU的高速网络大流检测算法[J].计算机研究与发展,2014,51(1):122-128)
[39]Zhang Zhen,Wang Binqiang,Lan Julong.Identifying elephant flows in Internet backbone traffic with Bloom filters and LRU[J].Computer Communications,2015,61:70-78
[40]Zhang Zhen,Wang Binqiang,Zhang Fengyu,et al.Traffic measurement algorithm based on least recent used and Bloom filter[J].Journal on Communications,2013,34(1):111-120(in Chinese)(张震,汪斌强,张风雨,等.基于LRU-BF策略的网络流量测量算法[J].通信学报,2013,34(1):111-120)
[41]Mitzenmacher M,V9cking B.The asymptotic of selecting the shortest of two,improved[C]Proc of the 37th Allerton Conf on Communication,Control,and Computing,Piscataway,NJ:IEEE,1999:326-327
[2]Benson T,Akella A,Maltz D A.Network traffic characteristics of data centers in the wild[C]Proc of the10th ACM SIGCOMM Conf on Internet Measurement.New York:ACM,2010:267-280
[3]Roy A,Zeng Hongyi,Bagga J,et al.Inside the social network’s(datacenter)network[J].ACM SIGCOMMComputer Communication Review,2015,45(4):123-137
[4]Mahajan R,Floyd S,Wetherall D.Controlling highbandwidth flows at the congested router[C]Proc of the 9th Int Conf on Network Protocols(ICNP).Piscataway,NJ:IEEE,2001:192-201
[5]Smitha,Kim I,Reddy A.Identifying long-term high bandwidth flows at a router[C]Proc of the 8th Int Conf on High Performance Computing.Piscataway,NJ:IEEE,2001:361-371
[6]Guo Liang,Matta I.The war between mice and elephants[C]Proc of the 9th Int Conf on Network Protocols(ICNP).Piscataway,NJ:IEEE,2001:180-188
[7]Alizadeh M,Greenberg A,Maltz D A,et al.Data center TCP(dcTCP)[J].ACM SIGCOMM Computer Communication Review,2010,40(4):63-74
[8]Fred B,Gorry F.IETF recommendations regarding active queue management,RFC 7567[S/OL].2015[2017-05-09].http:www.rfc-editor.org/info/rfc7567
[9]Papagiannakit K,Taft N,Diot C.Impact of flow dynamics on traffic engineering design principles[C]Proc of the 23rd IEEE INFOCOM.New York:IEEE Communications Society,2004:2295-2306
[10]Cui Weizhi,Ye Yu,Chen Qian.DiFS:Distributed flow scheduling for adaptive switching in Fat Tree data center networks[J].Computer Networks,2016:166-179
[11]Agarwal S,Kodialam M,Lakshman T V.Traffic engineering in software defined networks[C]Proc of the32nd IEEE INFOCOM.New York:IEEE Communications Society,2013:2211-2219
[12]Long Le,Aikat J,Jeffay K,et al.Differential congestion notification:Taming the elephants[C]Proc of the 12th IEEE Int Conf on Network Protocols.Piscataway,NJ:IEEE,2004:118-128
[13]Voorhies S,Lee H,Klappenecker A.Fair service for mice in the presence of elephants[J].Information Processing Letters,2006,99(3):96-101
[14]Estan C,Varghese G.New directions in traffic measurement and accounting:Focusing on the elephants,ignoring the mice[J].ACM Transactions on Computer Systems,2003,21(3):270-313
[15]Cisco Systems Incorporation.Cisco nexus 9500 platform common equipment data sheet[EB/OL].(2016-05-29)[2017-03-21].http:www.cisco.com/c/en/us/products/collateral/switches/nexus-9000-series-switches/datasheet-c78-729404.html
[16]Huawei Technology Incorporation.NetEngine5000Ecluster routers[EB/OL].[2017-04-25].http:e.huawei.com/en/products/enterprise-networking/routers/ne/ne5000e
[17]V9cking B.How asymmetry helps load balancing[J].Journal of the ACM,2003,50(4):568-589
[18]Che Lichang,Qiu Bin,Wu Hongren.Improvement of LRUcache for the detection and control of long-lived high bandwidth flows[J].Computer Communication,2005,29(1):103-113
[19]Choi Y,Joung J.A novel algorithm for detection of elephant flows:Landmark-LRU with recycle[G]Future Information Communication Technology and Applications.Berlin:Springer,2013:159-167
[20]Ben-Basat R,Einziger G,Friedman R,et al.Heavy hitters in streams and sliding windows[C]Proc of the 35th IEEEINFOCOM.New York:IEEE Communications Society,2016:1-9
[21]WIDE MAWI Working Group.MAWI working group traffic archive[OL].[2017-07-22].http:mawi.wide.ad.jp/mawi/
[22]Waikato WAND Network Research Group.Waikato Internet traffic storage[OL].[2017-01-12].http:wand.net.nz/wits/waikato/8/20110606-000000-0.php
[23]Benson T.Data set for IMC 2010data center measurement[OL].[2016-11-12].http:pages.cs.wisc.edu/~tbenson/IMC10_Data.html
[24]Cormode G,Muthukrishnan S.An improved data stream summary:The count-min sketch and its applications[J].Journal of Algorithms,2005,55(1):58-75
[25]Bai Lei,Chen Chao.Frequent items mining algorithm over high speed network flows based on double hash method[J].International Journal of Future Generation Communication and Networking,2016,9(5):75-82
[26]Chen Ling,Mei Qingling.Mining frequent items in data stream using time fading model[J].Information Sciences,2014,257:54-69
[27]Cafaroa M,Pulimenoa M,Epicocoa I,et al.Mining frequent items in the time fading model[J].Information Sciences,2016,(370/371):221-238
[28]Manku G,Motwani R.Approximate frequency counts over data streams[C]Proc of the 28th Int Conf on Very Large Databases.New York:ACM,2002:346-357
[29]Dimitropoulos X,Hurley P,Kind A.Probabilistic lossy counting:An efficient algorithm for finding heavy hitters[J].ACM SIGCOMM Computer Communication Review,2008,38(1):5-15
[30]Zhang Yu,Fang Binxing,Zhang Yongzheng.Identifying heavy hitters in high-speed network monitoring[J].Science China Information Sciences,2010,40(2):340-355(in Chinese)(张玉,方滨兴,张永铮.高速网络监控中大流量对象的识别[J].中国科学:信息科学,2010,40(2):340-355)
[31]Basat R B,Einziger G,Friedman R,et al.Optimal elephant flow detection[C]Proc of the 36th Annual IEEE Int Conf on Computer Communication.New York:IEEE Communications Society,2017:1-9
[32]Metwally A,Agrawal D,El Abbadi A.Efficient computation of frequent and top-k elements in data streams[C]Proc of the 10th Int Conf on Database Theory.Berlin:Springer,2005:398-412
[33]Carvalho P,Lima S R.Analyzing traffic flows through sampling:A comparative study[C]Proc of the 20th IEEESymp on Computers and Communication(ISCC).Piscataway,NJ:IEEE,2015:341-346
[34]Mori T,Uchida M,Kawahara R,et al.Identifying elephant flows through periodically sampled packets[C]Proc of the4th ACM SIGCOMM Conf on Internet Measurement.New York:ACM,2004:115-120
[35]Arasu A,Manku G S.Approximate counts and quantiles over sliding windows[C]Proc of the 23rd ACM SIGMOD-SIGACT-SIGART Symp on Principles of Database Systems.New York:ACM,2004:286-296
[36]Zhu Rui,Wang Bin,Luo Shiying,et al.Approximate continuous top-k query over sliding window[J].Journal of Computer Science and Technology,2017,32(1):93-109
[37]Kudo T,Takine T.Design of a sliding window scheme for detecting high packet-rate flows via random packet sampling[J].Computer Networks,2011,55(6):1351-1363
[38]Bai Lei,Tian Liqin,Chen Chao.A TCBF-LRU algorithm for identifying and measuring elephant flows in high speed network[J].Journal of Computer Research and Development,2014,51(1):122-128(in Chinese)(白磊,田立勤,陈超.基于TCBF-LRU的高速网络大流检测算法[J].计算机研究与发展,2014,51(1):122-128)
[39]Zhang Zhen,Wang Binqiang,Lan Julong.Identifying elephant flows in Internet backbone traffic with Bloom filters and LRU[J].Computer Communications,2015,61:70-78
[40]Zhang Zhen,Wang Binqiang,Zhang Fengyu,et al.Traffic measurement algorithm based on least recent used and Bloom filter[J].Journal on Communications,2013,34(1):111-120(in Chinese)(张震,汪斌强,张风雨,等.基于LRU-BF策略的网络流量测量算法[J].通信学报,2013,34(1):111-120)
[41]Mitzenmacher M,V9cking B.The asymptotic of selecting the shortest of two,improved[C]Proc of the 37th Allerton Conf on Communication,Control,and Computing,Piscataway,NJ:IEEE,1999:326-327
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |