short-survey

A survey on sliding window sketch for network measurement

Authors:

Kaimin WeiAuthors Info & Claims

Volume 226, Issue C

https://doi.org/10.1016/j.comnet.2023.109696

Published: 01 May 2023 Publication History

Abstract

As an important basis for network management, effective network measurement is critical for improving network performance and security. As an efficient tool for network measurement, sketch is a probabilistic data structure which can measure traffic statistics with low overhead. Considering that the most recent data of flows are more significant, sliding window sketch is proposed by combining sliding window model with the sketch. Sliding window sketch focuses on measuring information of the most recent period, e.g., data of the last N items or in the last N time units of measured traffic. By prioritizing the latest data, sliding window sketch can better reflect the current network situation and the future trend while avoiding information loss. However, implementation of sliding window sketch is very challenging considering the memory limitations of network devices and the need to maintain the window content in real-time. This paper conducts a comprehensive survey on the latest research works and provides insights into sliding window sketch. First, we briefly review the fundamentals of network measurement and sketch, and then we thoroughly go through and analyze the existing works on sliding window sketch for three different types. Afterwards, we provide a comparative analysis on the design of sliding window sketch in terms of data structures, supported operations, measurement tasks, implementation platforms and performance. Finally, we summarize this survey paper and highlight some future research directions.

References

[1]

Zhou Y., Alipourfard O., Yu M., Yang T., Accelerating network measurement in software, ACM SIGCOMM Comput. Commun. Rev. 48 (3) (2018) 2–12.

[2]

Jie L., Hongchang C., Penghao S., Tao H., Zhen Z., OrderSketch: An unbiased and fast sketch for frequency estimation of data streams, Comput. Netw. 201 (2021).

[3]

P. Roy, A. Khan, G. Alonso, Augmented sketch: Faster and more accurate stream processing, in: Proceedings of the 2016 International Conference on Management of Data, 2016, pp. 1449–1463.

[4]

D. Ting, Towards optimal cardinality estimation of unions and intersections with sketches, in: Proceedings of the ACM International Conference on Knowledge Discovery and Data Mining, SIGKDD, 2016, pp. 1195–1204.

[5]

Lai Y.-K., Wellem T., You H.-P., Hardware-assisted estimation of entropy norm for high-speed network traffic, Electron. Lett. 50 (24) (2014) 1845–1847.

[6]

Callegari C., Giordano S., Pagano M., An information-theoretic method for the detection of anomalies in network traffic, Comput. Secur. 70 (2017) 351–365.

[7]

T. Benson, A. Anand, A. Akella, M. Zhang, MicroTE: Fine grained traffic engineering for data centers, in: Proceedings of the Conference on Emerging Networking Experiments and Technologies, 2011, pp. 1–12.

[8]

Wu D., Cui L., A comprehensive survey on segment routing traffic engineering, Digit. Commun. Netw. (2022).

[9]

Dittmann G., Herkersdorf A., Network processor load balancing for high-speed links, in: Proceedings of the International Symposium on Performance Evaluation of Computer and Telecommunication Systems, 735, Citeseer, 2002.

[10]

Einziger G., Friedman R., Manes B., TinyLFU: A highly efficient cache admission policy, ACM Trans. Storage 13 (4) (2017) 1–31.

[11]

J. Jung, V. Paxson, A.W. Berger, H. Balakrishnan, Fast portscan detection using sequential hypothesis testing, in: Proceedings of the IEEE Symposium on Security and Privacy, 2004, pp. 211–225.

[12]

Zhang W., Kong F., Yang L., Chen Y., Zhang M., Hierarchical community detection based on partial matrix convergence using random walks, Tsinghua Sci. Technol. 23 (1) (2018) 35–46.

[13]

P. Phaal, S. Panchen, N. McKee, InMon corporation’s sFlow: A method for monitoring traffic in switched and routed networks, Tech. rep., 2001.

[14]

B. Claise, Cisco systems NetFlow services export version 9, Tech. rep., 2004.

[15]

J. Suh, T.T. Kwon, C. Dixon, W. Felter, J. Carter, OpenSample: A low-latency, sampling-based measurement platform for commodity SDN, in: IEEE International Conference on Distributed Computing Systems, 2014, pp. 228–237.

[16]

M. Yu, L. Jose, R. Miao, Software Defined Traffic Measurement with OpenSketch, in: USENIX Symposium on Networked Systems Design and Implementation, NSDI, 2013, pp. 29–42.

[17]

Liu L., Ding T., Feng H., Yan Z., Lu X., Tree sketch: An accurate and memory-efficient sketch for network-wide measurement, Comput. Commun. 194 (2022) 148–155.

[18]

Wellem T., Lai Y.-K., Sketch-guided filtering support for detecting superspreaders in high-speed networks, Electron. Lett. 52 (17) (2016) 1459–1461.

[19]

Y. Shi, M. Wen, C. Zhang, Incremental deployment of programmable switches for sketch-based network measurement, in: IEEE Symposium on Computers and Communications, ISCC, 2020, pp. 1–7.

[20]

T. Wellem, Y.-K. Lai, C.-Y. Huang, W.-Y. Chung, Toward hardware support for a flexible sketch-based network traffic monitoring system, in: IEEE Region 10 Symposium, TENSYMP, 2016, pp. 7–12.

[21]

B. Nagy, P. Orosz, P. Varga, Low-reaction time FPGA-based DDoS detector, in: IEEE/IFIP Network Operations and Management Symposium, NOMS, 2018, pp. 1–2.

[22]

Datar M., Gionis A., Indyk P., Motwani R., Maintaining stream statistics over sliding windows, SIAM J. Comput. 31 (6) (2002) 1794–1813.

Digital Library

[23]

Li S., Luo L., Guo D., Zhang Q., Fu P., A survey of sketches in traffic measurement: Design, optimization, application and implementation, 2020, arXiv preprint arXiv:2012.07214.

[24]

R.B. Basat, G. Einziger, I. Keslassy, A. Orda, S. Vargaftik, E. Waisbard, Memento: Making sliding windows efficient for heavy hitters, in: Proceedings of the International Conference on Emerging Networking EXperiments and Technologies, 2018, pp. 254–266.

[25]

Y. Zhou, Y. Zhou, S. Chen, Y. Zhang, Per-flow counting for big network data stream over sliding windows, in: IEEE/ACM International Symposium on Quality of Service (IWQoS), 2017, pp. 1–10.

[26]

Han H., Yan Z., Jing X., Pedrycz W., Applications of sketches in network traffic measurement: A survey, Inf. Fusion 82 (2022) 58–85.

[27]

M. Hasib, J.A. Schormans, Limitations of passive & active measurement methods in packet networks, in: London Communications Symposium (LCS), London, UK, 38, 2003.

[28]

C. Tan, Z. Jin, C. Guo, T. Zhang, H. Wu, K. Deng, D. Bi, D. Xiang, NetBouncer: Active Device and Link Failure Localization in Data Center Networks, in: USENIX Symposium on Networked Systems Design and Implementation, NSDI, 2019, pp. 599–614.

[29]

C. Guo, L. Yuan, D. Xiang, Y. Dang, R. Huang, D. Maltz, Z. Liu, V. Wang, B. Pang, H. Chen, et al., Pingmesh: A large-scale system for data center network latency measurement and analysis, in: Proceedings of the ACM Conference on Special Interest Group on Data Communication, 2015, pp. 139–152.

[30]

Nobre J.C., Mozzaquatro B.A., Granville L.Z., Network-wide initiatives to control measurement mechanisms: a survey, IEEE Commun. Surv. Tutor. 20 (2) (2018) 1475–1491.

[31]

M. Jarschel, T. Zinner, T. Höhn, P. Tran-Gia, On the accuracy of leveraging SDN for passive network measurements, in: IEEE Australasian Telecommunication Networks and Applications Conference, ATNAC, 2013, pp. 41–46.

[32]

Y. Zhang, Z. Liu, R. Wang, T. Yang, J. Li, R. Miao, P. Liu, R. Zhang, J. Jiang, CocoSketch: high-performance sketch-based measurement over arbitrary partial key query, in: Proceedings of the ACM SIGCOMM Conference, 2021, pp. 207–222.

[33]

Zhang X., Cui L., Tso F.P., Jia W., pHeavy: Predicting heavy flows in the programmable data plane, IEEE Trans. Netw. Serv. Manag. 18 (4) (2021) 4353–4364.

[34]

P. Calyam, D. Krymskiy, M. Sridharan, P. Schopis, Active and passive measurements on campus, regional and national network backbone paths, in: Proceedings of the IEEE International Conference on Computer Communications and Networks, ICCCN, 2005, pp. 537–542.

[35]

Q. Zhao, J. Xu, Z. Liu, Design of a novel statistics counter architecture with optimal space and time efficiency, in: Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems, 2006, pp. 323–334.

[36]

Pagiamtzis K., Sheikholeslami A., Content-addressable memory (CAM) circuits and architectures: A tutorial and survey, IEEE J. Solid-State Circuits 41 (3) (2006) 712–727.

[37]

Lu Y., Montanari A., Prabhakar B., Dharmapurikar S., Kabbani A., Counter braids: a novel counter architecture for per-flow measurement, ACM SIGMETRICS Perform. Eval. Rev. 36 (1) (2008) 121–132.

[38]

Y. Du, H. Huang, Y.-E. Sun, S. Chen, G. Gao, Self-adaptive sampling for network traffic measurement, in: IEEE Conference on Computer Communications, INFOCOM, 2021, pp. 1–10.

[39]

C. Zhang, R. Green, Communication security in internet of thing: preventive measure and avoid DDoS attack over IoT network, in: Proceedings of the Symposium on Communications & Networking, 2015, pp. 8–15.

[40]

Li P., Salour M., Su X., A survey of Internet worm detection and containment, IEEE Commun. Surv. Tutor. 10 (1) (2008) 20–35.

Digital Library

[41]

J. Gadge, A.A. Patil, Port scan detection, in: IEEE International Conference on Networks, 2008, pp. 1–6.

[42]

L. Tang, Q. Huang, P.P. Lee, SpreadSketch: Toward invertible and network-wide detection of superspreaders, in: IEEE Conference on Computer Communications, INFOCOM, 2020, pp. 1608–1617.

[43]

Z. Liu, A. Manousis, G. Vorsanger, V. Sekar, V. Braverman, One sketch to rule them all: Rethinking network flow monitoring with univmon, in: Proceedings of the ACM SIGCOMM Conference, 2016, pp. 101–114.

[44]

Cormode G., Muthukrishnan S., An improved data stream summary: The count-min sketch and its applications, in: Latin American Symposium on Theoretical Informatics, Springer, 2004, pp. 29–38.

[45]

C. Estan, G. Varghese, New directions in traffic measurement and accounting, in: Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, 2002, pp. 323–336.

[46]

Charikar M., Chen K., Farach-Colton M., Finding frequent items in data streams, in: International Colloquium on Automata, Languages, and Programming, Springer, 2002, pp. 693–703.

[47]

Bloom B.H., Space/time trade-offs in hash coding with allowable errors, Commun. ACM 13 (7) (1970) 422–426.

Digital Library

[48]

C.H. Song, P.G. Kannan, B.K.H. Low, M.C. Chan, Fcm-Sketch: generic network measurements with data plane support, in: Proceedings of the 16th International Conference on Emerging Networking EXperiments and Technologies, 2020, pp. 78–92.

[49]

T. Yang, J. Jiang, P. Liu, Q. Huang, J. Gong, Y. Zhou, R. Miao, X. Li, S. Uhlig, Elastic sketch: Adaptive and fast network-wide measurements, in: Proceedings of the Conference of the ACM Special Interest Group on Data Communication, 2018, pp. 561–575.

[50]

Z. Liu, R. Ben-Basat, G. Einziger, Y. Kassner, V. Braverman, R. Friedman, V. Sekar, NitroSketch: Robust and general sketch-based monitoring in software switches, in: Proceedings of the ACM Special Interest Group on Data Communication, 2019, pp. 334–350.

[51]

Assaf E., Basat R.B., Einziger G., Friedman R., Pay for a sliding bloom filter and get counting, distinct elements, and entropy for free, in: IEEE Conference on Computer Communications, INFOCOM, IEEE, 2018, pp. 2204–2212.

[52]

Zhou Y., Bi J., Yang T., Gao K., Cao J., Zhang D., Wang Y., Zhang C., HyperSight: Towards scalable, high-coverage, and dynamic network monitoring queries, IEEE J. Sel. Areas Commun. 38 (6) (2020) 1147–1160.

[53]

L. Golab, D. DeHaan, E.D. Demaine, A. Lopez-Ortiz, J.I. Munro, Identifying frequent items in sliding windows over on-line packet streams, in: Proceedings of the ACM SIGCOMM Conference on Internet Measurement, 2003, pp. 173–178.

[54]

Cui Y., Qian Q., Guo C., Shen G., Tian Y., Xing H., Yan L., Towards DDoS detection mechanisms in software-defined networking, J. Netw. Comput. Appl. 190 (2021).

Digital Library

[55]

A. Zhou, H. Zhu, L. Liu, C. Zhu, Identification of heavy hitters for network data streams with probabilistic sketch, in: IEEE International Conference on Cloud Computing and Big Data Analysis, ICCCBDA, 2018, pp. 451–456.

[56]

Turkovic B., Oostenbrink J., Kuipers F., Keslassy I., Orda A., Sequential zeroing: Online heavy-hitter detection on programmable hardware, in: IFIP Networking Conference (Networking), IEEE, 2020, pp. 422–430.

[57]

R. Shahout, R. Friedman, D. Adas, CELL: Counter Estimation for Per-flow Traffic in Streams and Sliding Windows, in: IEEE International Conference on Network Protocols, ICNP, 2021, pp. 1–12.

[58]

S. Sun, J. Zheng, D. Li, HEE-Sketch: an Efficient Sketch for Sliding-Window Frequency Estimation over Skewed Data Streams, in: IEEE International Conference on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom), 2019, pp. 736–743.

[59]

R. Ben-Basat, G. Einziger, R. Friedman, Y. Kassner, Heavy hitters in streams and sliding windows, in: IEEE International Conference on Computer Communications, INFOCOM, 2016, pp. 1–9.

[60]

Y. Chabchoub, G. Heébrail, Sliding Hyperloglog: Estimating cardinality in a data stream over a sliding window, in: IEEE International Conference on Data Mining Workshops, 2010, pp. 1297–1303.

[61]

Tang H., Wu Y., Li T., Han C., Ge J., Zhao X., Efficient identification of TOP-K heavy hitters over sliding windows, Mob. Netw. Appl. 24 (5) (2019) 1732–1741.

[62]

X. Chen, S.L. Feibish, Y. Koral, J. Rexford, O. Rottenstreich, S.A. Monetti, T.-Y. Wang, Fine-grained queue measurement in the data plane, in: Proceedings of the International Conference on Emerging Networking Experiments and Technologies, 2019, pp. 15–29.

[63]

S. Matusevych, A.J. Smola, A. Ahmed, Hokusai−sketching streams in real time, in: Proceedings of the Conference on Uncertainty in Artificial Intelligence, 2012, pp. 594–603.

[64]

A. Shrivastava, A.C. Konig, M. Bilenko, Time adaptive sketches (Ada-sketches) for summarizing data streams, in: Proceedings of the International Conference on Management of Data, 2016, pp. 1417–1432.

[65]

Shan J., Fu Y., Ni G., Luo J., Wu Z., Fast counting the cardinality of flows for big traffic over sliding windows, Front. Comput. Sci. 11 (1) (2017) 119–129.

Digital Library

[66]

D. Adas, R. Friedman, Sliding Window CRDT Sketches, in: IEEE International Symposium on Reliable Distributed Systems, SRDS, 2021, pp. 288–298.

[67]

Papapetrou O., Garofalakis M., Deligiannakis A., Sketch-based querying of distributed sliding-window data streams, Proc. VLDB Endow. 5 (10) (2012).

[68]

P. Chen, D. Chen, L. Zheng, J. Li, T. Yang, Out of many we are one: Measuring item batch with clock-sketch, in: Proceedings of the International Conference on Management of Data, 2021, pp. 261–273.

[69]

X. Gou, L. He, Y. Zhang, K. Wang, X. Liu, T. Yang, Y. Wang, B. Cui, Sliding sketches: A framework using time zones for data stream processing in sliding windows, in: Proceedings of the ACM International Conference on Knowledge Discovery & Data Mining, SIGKDD, 2020, pp. 1015–1025.

[70]

T. Li, S. Chen, Y. Ling, Fast and compact per-flow traffic measurement through randomized counter sharing, in: Proceedings IEEE INFOCOM, 2011, pp. 1799–1807.

[71]

G. Einziger, R. Friedman, Counting with tinytable: Every bit counts!, in: Proceedings of the International Conference on Distributed Computing and Networking, 2016, pp. 1–10.

[72]

Morris R., Counting large numbers of events in small registers, Commun. ACM 21 (10) (1978) 840–842.

Digital Library

[73]

Y. Zhu, N. Kang, J. Cao, A. Greenberg, G. Lu, R. Mahajan, D. Maltz, L. Yuan, M. Zhang, B.Y. Zhao, et al., Packet-level telemetry in large datacenter networks, in: Proceedings of the ACM Conference on Special Interest Group on Data Communication, 2015, pp. 479–491.

[74]

D. Yu, Y. Zhu, B. Arzani, R. Fonseca, T. Zhang, K. Deng, L. Yuan, dShark: A General, Easy to Program and Scalable Framework for Analyzing In-network Packet Traces, in: USENIX Symposium on Networked Systems Design and Implementation, NSDI, 2019, pp. 207–220.

[75]

J. Sonchack, A.J. Aviv, E. Keller, J.M. Smith, TurboFlow: Information rich flow record generation on commodity switches, in: Proceedings of the EuroSys Conference, 2018, pp. 1–16.

[76]

Y. Li, R. Miao, C. Kim, M. Yu, FlowRadar: A Better NetFlow for Data Centers, in: USENIX Symposium on Networked Systems Design and Implementation, NSDI, 2016, pp. 311–324.

[77]

C. Zhang, J. Bi, Y. Zhou, J. Wu, B. Liu, Z. Li, A.B. Dogar, Y. Wang, P4DB: On-the-fly debugging of the programmable data plane, in: IEEE International Conference on Network Protocols, ICNP, 2017, pp. 1–10.

[78]

C. Zhang, J. Bi, Y. Zhou, A.B. Dogar, J. Wu, HyperV: A high performance hypervisor for virtualization of the programmable data plane, in: IEEE International Conference on Computer Communication and Networks, ICCCN, 2017, pp. 1–9.

[79]

D. Hancock, J. Van der Merwe, Hyper4: Using P4 to virtualize the programmable data plane, in: Proceedings of the International on Conference on Emerging Networking EXperiments and Technologies, 2016, pp. 35–49.

[80]

Datar M., Motwani R., The sliding-window computation model and results, in: Data Stream Management, Springer, 2016, pp. 149–165.

[81]

Y. Zhou, P. Liu, H. Jin, T. Yang, S. Dang, X. Li, One memory access sketch: a more accurate and faster sketch for per-flow measurement, in: IEEE Global Communications Conference, GLOBECOM, 2017, pp. 1–6.

[82]

Yang T., Zhou Y., Jin H., Chen S., Li X., Pyramid sketch: A sketch framework for frequency estimation of data streams, Proc. VLDB Endow. 10 (11) (2017) 1442–1453.

[83]

Metwally A., Agrawal D., Abbadi A.E., Efficient computation of frequent and top-k elements in data streams, International Conference on Database Theory, Springer, 2005, pp. 398–412.

[84]

Flajolet P., Fusy É., Gandouet O., Meunier F., Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm, in: Discrete Mathematics and Theoretical Computer Science, Discrete Mathematics and Theoretical Computer Science, 2007, pp. 137–156.

[85]

A. Kuzmanovic, E.W. Knightly, Low-rate TCP-targeted denial of service attacks: the shrew vs. the mice and elephants, in: Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, 2003, pp. 75–86.

[86]

Adams R., Active queue management: A survey, IEEE Commun. Surv. Tutor. 15 (3) (2012) 1425–1476.

[87]

, Wikipedia, Dolby noise−reduction system, [EB/OL], https://en.wikipedia.org/wiki/Dolby_noise-reduction_system, (Accessed November 8, 2022).

[88]

Whang K.-Y., Vander-Zanden B.T., Taylor H.M., A linear-time probabilistic counting algorithm for database applications, ACM Trans. Database Syst. 15 (2) (1990) 208–229.

Digital Library

[89]

O’neil E.J., O’neil P.E., Weikum G., The LRU-K page replacement algorithm for database disk buffering, Acm Sigmod Record 22 (2) (1993) 297–306.

[90]

Shapiro M., Preguiça N., Baquero C., Zawirski M., Conflict-free replicated data types, in: Symposium on Self-Stabilizing Systems, Springer, 2011, pp. 386–400.

[91]

Yang T., Zhang H., Li J., Gong J., Uhlig S., Chen S., Li X., HeavyKeeper: An accurate algorithm for finding top-k elephant flows, IEEE/ACM Trans. Netw. 27 (5) (2019) 1845–1858.

[92]

Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Introduction to algorithms, MIT Press, 2022.

[93]

Einziger G., Friedman R., TinySet-an access efficient self adjusting Bloom filter construction, IEEE/ACM Trans. Netw. 25 (4) (2017) 2295–2307.

[94]

Bosshart P., Daly D., Gibb G., Izzard M., McKeown N., Rexford J., Schlesinger C., Talayco D., Vahdat A., Varghese G., et al., P4: Programming protocol-independent packet processors, ACM SIGCOMM Comput. Commun. Rev. 44 (3) (2014) 87–95.

Digital Library

[95]

Zhang Y., Li J., Lei Y., Yang T., Li Z., Zhang G., Cui B., On-off sketch: A fast and accurate sketch on persistence, Proc. VLDB Endow. 14 (2) (2020) 128–140.

[96]

Zilberman N., Audzevich Y., Covington G.A., Moore A.W., NetFPGA SUME: Toward 100 Gbps as research commodity, IEEE Micro 34 (5) (2014) 32–41.

[97]

Linguaglossa L., Lange S., Pontarelli S., Rétvári G., Rossi D., Zinner T., Bifulco R., Jarschel M., Bianchi G., Survey of performance acceleration techniques for network function virtualization, Proc. IEEE 107 (4) (2019) 746–764.

[98]

Zhang X., Cui L., Wei K., Tso F.P., Ji Y., Jia W., A survey on stateful data plane in software defined networks, Comput. Netw. 184 (2021).

[99]

Michel O., Bifulco R., Retvari G., Schmid S., The programmable data plane: abstractions, architectures, algorithms, and applications, ACM Comput. Surv. 54 (4) (2021) 1–36.

[100]

Bhoedjang R.A., Ruhl T., Bal H.E., User-level network interface protocols, Computer 31 (11) (1998) 53–60.

[101]

K. Deierling, What Is a SmartNIC?, [EB/OL], https://blogs.nvidia.com/blog/2021/10/29/what-is-a-smartnic/, (Accessed October 20, 2022).

[102]

Y. Qiu, J. Xing, K.-F. Hsu, Q. Kang, M. Liu, S. Narayana, A. Chen, Automated SmartNIC offloading insights for network functions, in: Proceedings of the ACM Symposium on Operating Systems Principles, SIGOPS, 2021, pp. 772–787.

[103]

J. Kim, I. Jang, W. Reda, J. Im, M. Canini, D. Kostić, Y. Kwon, S. Peter, E. Witchel, LineFS: Efficient SmartNIC Offload of a Distributed File System with Pipeline Parallelism, in: Proceedings of the ACM Symposium on Operating Systems Principles, SIGOPS, 2021, pp. 756–771.

[104]

. Intel Corporation, Intel Tofino, [EB/OL], https://www.intel.com/content/www/us/en/products/network-io/programmable-ethernet-switch/tofino-3-brief.html, (Accessed November 15, 2022).

[105]

R. Bifulco, G. Rétvári, A survey on the programmable data plane: Abstractions, architectures, and open problems, in: IEEE International Conference on High Performance Switching and Routing, HPSR, 2018, pp. 1–7.

[106]

V. Sivaraman, S. Narayana, O. Rottenstreich, S. Muthukrishnan, J. Rexford, Heavy-hitter detection entirely in the data plane, in: Proceedings of the Symposium on SDN Research, 2017, pp. 164–176.

[107]

R. Ben-Basat, X. Chen, G. Einziger, O. Rottenstreich, Efficient measurement on programmable switches using probabilistic recirculation, in: IEEE International Conference on Network Protocols, ICNP, 2018, pp. 313–323.

[108]

Z. Hang, Y. Shi, M. Wen, W. Quan, C. Zhang, SWAP: A sliding window algorithm for in-network packet measurement, in: Proceedings of the International Conference on High Performance Compilation, Computing and Communications, 2019, pp. 84–89.

[109]

Qian M., Cui L., Zhang X., Tso F.P., Deng Y., dDrops: Detecting silent packet drops on programmable data plane, Comput. Netw. 214 (2022).

[110]

Zhang X., Cui L., Tso F.P., Li Z., Jia W., Dapper: Deploying service function chains in the programmable data plane via deep reinforcement learning, IEEE Trans. Serv. Comput. (2023).

[111]

P. Cui, H. Pan, Z. Li, J. Wu, S. Zhang, X. Yang, H. Guan, G. Xie, NetFC: Enabling accurate floating-point arithmetic on programmable switches, in: IEEE International Conference on Network Protocols, ICNP, 2021, pp. 1–11.

[112]

Xu Y., Dong D., Xu W., Liao X., SketchDLC: A sketch on distributed deep learning communication via trace capturing, ACM Trans. Archit. Code Optim. 16 (2) (2019) 1–26.

[113]

B. Wang, Z. Liu, An accurate network measurement framework combining SVM with sketch, in: IEEE Joint International Information Technology and Artificial Intelligence Conference, ITAIC, 2019, pp. 89–95.

[114]

Y. Zhao, Z. Zhong, Y. Li, Y. Zhou, Y. Zhu, L. Chen, Y. Wang, T. Yang, Cluster-Reduce: Compressing Sketches for Distributed Data Streams, in: Proceedings of the ACM Conference on Knowledge Discovery & Data Mining, SIGKDD, 2021, pp. 2316–2326.

[115]

X. Chen, S. Landau-Feibish, M. Braverman, J. Rexford, BeauCoup: Answering many network traffic queries, one memory update at a time, in: Proceedings of the Annual Conference of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication, 2020, pp. 226–239.

Cited By

Wu YJiang SDong SZhong ZChen JHu YYang TUhlig SCui BSingh ASun YAkoglu LGunopulos DYan XKumar ROzcan FYe J(2023)MicroscopeSketch: Accurate Sliding Estimation Using Adaptive ZoomingProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599432(2660-2671)Online publication date: 6-Aug-2023
https://dl.acm.org/doi/10.1145/3580305.3599432

Recommendations

HBL-Sketch: A New Three-Tier Sketch for Accurate Network Measurement
Algorithms and Architectures for Parallel Processing
Abstract
Network measurement is critical for many network functions such as detecting network anomalies, accounting, detecting elephant flow and congestion control. Recently, sketch based solutions are widely used for network measurement because of two ...
Sliding Sketches: A Framework using Time Zones for Data Stream Processing in Sliding Windows
KDD '20: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

Data stream processing has become a hot issue in recent years due to the arrival of big data era. There are three fundamental stream processing tasks: membership query, frequency query and heavy hitter query. While most existing solutions address these ...
Data Stream Grouping Aggregate Algorithms Based on Compound Sliding Window
ISCSCT '08: Proceedings of the 2008 International Symposium on Computer Science and Computational Technology - Volume 02

Grouping aggregate queries Based on Sliding Window is a focus problem in data stream research. Among existing research works, the grouping aggregate algorithms are presented for immediate continuous queries, and they didn’t take into consideration the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computer Networks: The International Journal of Computer and Telecommunications Networking

Computer Networks: The International Journal of Computer and Telecommunications Networking Volume 226, Issue C

May 2023

173 pages

ISSN:1389-1286

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 01 May 2023

Author Tags

Qualifiers

Short-survey

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wu YJiang SDong SZhong ZChen JHu YYang TUhlig SCui BSingh ASun YAkoglu LGunopulos DYan XKumar ROzcan FYe J(2023)MicroscopeSketch: Accurate Sliding Estimation Using Adaptive ZoomingProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599432(2660-2671)Online publication date: 6-Aug-2023
https://dl.acm.org/doi/10.1145/3580305.3599432

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents