Computer Science

Computer Science ›› 2024, Vol. 51 ›› Issue (4): 48-55.doi: 10.11896/jsjkx.231000213

• Compact Data Structure • Previous Articles     Next Articles

RBFRadar:Detecting Remarkable Burst Flows with Programmable Data Plane

WU Yanni1,2, ZHOU Zhengyan3, CHEN Hanze1, ZHANG Dong2,4   

  1. 1 College of Computer and Data Science,Fuzhou University,Fuzhou 350108,China
    2 Quan Cheng Laboratory,Jinan 250100,China
    3 College of Computer Science and Technology,Zhejiang University,Hangzhou 310013,China
    4 Zhicheng College,Fuzhou University,Fuzhou 350002,China
  • Received:2023-10-29 Revised:2024-01-26 Online:2024-04-15 Published:2024-04-10
  • Supported by:
    National Key R & D Program of China(2023YFB2904000,2023YFB2904005),Quan Cheng Laboratory(QCLZD202304) and Research Project of Provincial Laboratory of Shandong,China(SYS202201).

PDF (PC)

95

Abstract: Burst is a common and important traffic pattern in diverse network traffics.Since bursts may increase network latency and have a non-trivial impact on application performance,the efforts to detect,analyze and mitigate burst flows are meaningful for improving the performance and robustness of network.However,existing per-burst-based detection schemes face the limitations of significant bandwidth overheads and high user burdens.This paper proposes the detection of remarkable burst flows(RBFs) via observing and analyzing the characteristics of burst flows in various scenarios.The detection of RBFs reduces the bandwidth overheads.At the same time,such detection process avoids the requirements of intensive manual labor and expert experience,and mitigate the burdens of network operators.We propose RBFRadar,a Sketch-based RBF detection framework that supports RBF detection on programmable data plane,observing flow-level burstiness in a period.We prototype RBFRadar in PISA architecture with limited memory footprints and low time complexity.Experiments demonstrate that the F1-score of RBFRadar in RBF detection is 5.6 times to 23.4 times higher than that of existing schemes.Compared with per-burst detection,the bandwidth overhead could be reduced by 84.62% to 98.84%.

Key words: Burst flow detection, Sketch, Network measurement, Programmable data plane, Data center network

CLC Number: 

  • TP393
[1]GHABASHNEH E,ZHAO Y,LUMEZANU C,et al.A microscopic view of bursts,buffer contention,and loss in data centers[C]//Proceedings of the 22nd ACM Internet Measurement Conference.2022:567-580.
[2]SHARAFZADEH E,ABDOUS S,GHORBANI S.Understan-ding the impact of host networking elements on traffic bursts[C]//20th USENIX Symposium on Networked Systems Design and Implementation(NSDI 23).2023:237-254.
[3]PAXSON V,FLOYD S.Wide area traffic:the failure of Poisson modeling[J].IEEE/ACM Transactions on Networking,1995,3(3):226-244.
[4]KIM G,LEE W.Absorbing microbursts without headroom fordata center networks[J].IEEE Communications Letters,2019,23(5):806-809.
[5]FLACH T,DUKKIPATI N,TERZIS A,et al.Reducing web latency:the virtue of gentle aggression[C]//Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM.2013:159-170.
[6]SHAN D,REN F,CHENG P,et al.Micro-burst in data centers:Observations,analysis,and mitigations[C]//2018 IEEE 26th International Conference on Network Protocols(ICNP).IEEE,2018:88-98.
[7]CHEN X,FEIBISH S L,KORAL Y,et al.Catching the microburst culprits with snappy[C]//Proceedings of the Afternoon Workshop on Self-Driving Networks.2018:22-28.
[8]ZHONG Z,YAN S,LI Z,et al.BurstSketch:Finding bursts in data streams[C]//Proceedings of the 2021 International Confe-rence on Management of Data.2021:2375-2383.
[9]JOSHI R,QU T,CHAN M C,et al.BurstRadar:Practical real-time microburst monitoring for datacenter networks[C]//Proceedings of the 9th Asia-Pacific Workshop on Systems.2018:1-8.
[10]GAO K,LI D,WANG S.Bandwidth-efficient Microburst Mea-surement in Large-scale Datacenter Networks[C]//Asia-Pacific Workshop on Networking.2022.
[11]BOSSHART P,DALY D,GIBB G,et al.P4:Programming protocol-independent packet processors[J].ACM SIGCOMM Computer Communication Review,2014,44(3):87-95.
[12]KAPOOR R,SNOEREN A C,VOELKER G M,et al.Bullet trains:A study of NIC burst behavior at microsecond timescales[C]//Proceedings of the Ninth ACM Conference on Emerging Networking Experiments and Technologies.2013:133-138.
[13]ZHANG Q,LIU V,ZENG H,et al.High-resolution measurement of data center microbursts[C]//Proceedings of the 2017 Internet Measurement Conference.2017:78-85.
[14]SCHERRER S,VLIEGEN J,SATEESAN A,et al.ALBUS:a Probabilistic Monitoring Algorithm to Counter Burst-Flood Attacks[J].arXiv:2306.14328,2023.
[15]SUN H,LUI J C S,YAU D K Y.Defending against low-rate TCP attacks:Dynamic detection and protection[C]//Procee-dings of the 12th IEEE International Conference on Network Protocols(ICNP 2004).IEEE,2004:196-205.
[16]ALCOZ A G,STROHMEIER M,LENDERS V,et al.Aggregate-based congestion control for pulse-wave DDoS defense[C]//Proceedings of the ACM SIGCOMM 2022 Conference.2022:693-706.
[17]REZAEI H.Adaptive Microburst Control Techniques in Incast-Heavy Datacenter Networks[D].Chicago:University of Illinois,2021.
[18]TANG D,ZHANG S,CHEN J,et al.The detection of low-rate DoS attacks using the SADBSCAN algorithm[J].Information Sciences,2021,565:229-247.
[19]TAMMANA P,AGARWAL R,LEE M.Simplifying datacenter network debugging with {PathDump}[C]//12th USENIX Symposium on Operating Systems Design and Implementation(OSDI 16).2016:233-248.
[20]ARZANI B,CIRACI S,CHAMON L,et al.007:Democratically finding the cause of packet drops[C]//15th USENIX Sympo-sium on Networked Systems Design and Implementation(NSDI 18).2018:419-435.
[21]GKOUNIS D,KOTRONIS V,LIASKOS C,et al.On the interplay of link-flooding attacks and traffic engineering[J].ACM SIGCOMM Computer Communication Review,2016,46(2):5-11.
[22]MAI L,HONG C,COSTA P.Optimizing network performance in distributed machine learning[C]//7th USENIX Workshop on Hot Topics in Cloud Computing,2015.
[23]ZAHARIA M,CHOWDHURY M,FRANKLIN M J,et al.Spark:Cluster computing with working sets[C]//2nd USENIX Workshop on Hot Topics in Cloud Computing(HotCloud 10).2010.
[24]REZAEI H,VAMANAN B.Superways:A datacenter topology for incast-heavy workloads[C]//Proceedings of the Web Conference 2021.2021:317-328.
[25]YUE M,WU Z,WANG J.Detecting LDoS attack bursts based on queue distribution[J].IET Information Security,2019,13(3):285-292.
[26]SPITERI K,URGAONKAR R,SITARAMAN R K.BOLA:Near-optimal bitrate adaptation for online videos[J].IEEE/ACM Transactions on Networking,2020,28(4):1698-1711.
[27]BLEULER S,LAUMANNS M,THIELE L,et al.PISA—a platform and programming language independent interface for search algorithms[C]//Evolutionary Multi-Criterion Optimization:Second International Conference,EMO 2003,Faro,Portugal.Berlin Heidelberg:Springer,2003:494-508.
[28]ZHANG Y,LIU Z,WANG R,et al.CocoSketch:High-perfor-mance Sketch-based measurement over arbitrary partial key query[C]//Proceedings of the 2021 ACM SIGCOMM 2021 Conference.2021:207-222.
[29] CORMODE G,MUTHUKRISHNAN S.An Improved DataStream Summary:The Count-min Sketch and its Applications[J].Journal of Algorithms,2005,55(1):58-75.
[30]TANG L,HUANG Q,LEE P P C.Mv-Sketch:A fast and compact invertible Sketch for heavy flow detection in network data streams[C]//IEEE INFOCOM 2019-IEEE Conference on Computer Communications.IEEE,2019:2026-2034.
[31]HUANG Q,LEE P P C.A hybrid local and distributed Ske-tching design for accurate and scalable heavy key detection in network data streams[J].Computer Networks,2015,91:298-315.
[32]2020.Barefoot Tofino[OL].(2020).https://barefootnetworks.com/products/brief-tofino/.
[33]BOYER R S,MOORE J S.MJRTY－A Fast Majority Vote Algorithm[M]//Automated reasoning:essays in honor of Woody Bledsoe.Dordrecht:Springer Netherlands,1991:105-117.
[34]BMv2 Software Switch[OL].http://bmv2.org/.
[35]LV J W.Microburst detection based on programmable switch [D].Hangzhou:Zhejiang University,2023.
[36]WANG H,MELISSOURGOS D,MA C,et al.Real-time Spread Burst Detection in Data Streaming[J].Proceedings of the ACM on Measurement and Analysis of Computing Systems,2023,7(2):1-31.
[37]PAUL D,PENG Y,LI F.Bursty event detection throughout histories[C]//2019 IEEE 35th International Conference on Data Engineering(ICDE).IEEE,2019:1370-1381.
[38]XIE W,ZHU F,JIANG J,et al.TopicSketch:Real-time bursty topic detection from twitter[J].IEEE Transactions on Know-ledge and Data Engineering,2016,28(8):2216-2229.
[1] CHEN Xinyang, CHEN Hanze, ZHOU Jiasheng, HUANG Jiaqing, YU Jiashuo, ZHU Longlong, ZHANG Dong. IntervalSketch:Approximate Statistical Method for Interval Items in Data Stream [J]. Computer Science, 2024, 51(4): 4-10.
[2] MAO Chenyu, HUANG He, SUN Yu'e, DU Yang. Global Top-K Frequent Flow Measurement for Continuous Periods in Distributed Networks [J]. Computer Science, 2024, 51(4): 28-38.
[3] XIAO Zhaobin, CUI Yunhe, CHEN Yi, SHEN Guowei, GUO Chun, QIAN Qing. EAGLE:A Network Telemetry Mechanism Based on Telemetry Data Graph in Kernel and UserMode [J]. Computer Science, 2024, 51(2): 311-321.
[4] PAN Zhi-yong, CHENG Bao-lei, FAN Jian-xi, BIAN Qing-rong. Algorithm to Construct Node-independent Spanning Trees in Data Center Network BCDC [J]. Computer Science, 2022, 49(7): 287-296.
[5] DOU Zhi, WANG Ning, WANG Shi-jie, WANG Zhi-hui, LI Hao-jie. Sketch Colorization Method with Drawing Prior [J]. Computer Science, 2022, 49(4): 195-202.
[6] YI Yi, FAN Jian-xi, WANG Yan, LIU Zhao, DONG Hui. Fault-tolerant Routing Algorithm in BCube Under 2-restricted Connectivity [J]. Computer Science, 2021, 48(6): 253-260.
[7] ZHANG Deng-ke, WANG Xing-wei, HE Qiang, ZENG Rong-fei, YI bo. State-of-the-art Survey on Reconfigurable Data Center Networks [J]. Computer Science, 2021, 48(3): 246-258.
[8] TAN Ling-ling, YANG Fei, YI Jun-kai. Optimization Study of Sketch Algorithm Based on AVX Instruction Set [J]. Computer Science, 2021, 48(11A): 585-587.
[9] ZHAO Qian, CHEN Shu-hui. LRBG-based Approach for IP Geolocation [J]. Computer Science, 2020, 47(11A): 291-295.
[10] LI Zong-min, LI Si-yuan, LIU Yu-jie, LI Hua. Sketch-based Image Retrieval Based on Attention Model [J]. Computer Science, 2020, 47(11): 199-204.
[11] JIN Yong, LIU Yi-xing, WANG Xin-xin. SDN-based Multipath Traffic Scheduling Algorithm for Data Center Network [J]. Computer Science, 2019, 46(6): 90-94.
[12] YU Mei-yu, WU Hao, GUO Xiao-yan, JIA Qi GUO He. Sequential Feature Based Sketch Recognition [J]. Computer Science, 2018, 45(11A): 198-202.
[13] FAN Zi-fu, LI Shu and ZHANG Dan. Traffic Scheduling Based Congestion Control Algorithm for Data Center Network on Software Defined Network [J]. Computer Science, 2017, 44(Z6): 266-269.
[14] QIAO Yan, JIAO Jun and RAO Yuan. Traffic Estimation for Data Center Network Based on Traffic Characteristics [J]. Computer Science, 2017, 44(2): 171-175.
[15] JI Hai-feng and TIAN Huai-wen. Sketch Recognition Method of Combined Graphs for Conceptual Design [J]. Computer Science, 2016, 43(Z6): 134-138.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.