nach oben

Journal of Network and Systems Management

Erschienen in:

30.07.2020

BitMatrix: A Multipurpose Sketch for Monitoring of Multi-tenant Networks

verfasst von: Regis Francisco Teles Martins, Rodolfo da Silva Villaça, Fábio Luciano Verdi

Erschienen in: Journal of Network and Systems Management | Ausgabe 4/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Sketches are probabilistic data structures capable of summarizing and storing network data (packets, bytes, and flows), with a certain degree of accuracy, that have become widely popular for network measurement and monitoring. In this paper, we propose a new multi-purpose sketch, called BitMatrix, which is capable of working in multi-tenant networks. Owing to its multi-dimensional architecture, BitMatrix can differentiate between bit markings and byte/packet counting from different sources in a network. As a multi-purpose sketch, BitMatrix and its algorithms contribute to the literature by providing information regarding the paths traversed by each packet and are designed for use in multi-tenant networks. We also designed a statistical model to adjust the measurements owing to the probabilistic behavior of the sketches. Such a model is able to infer the standard error rate and approximate the BitMatrix counters to the real value. The adjusted BitMatrix measurement has a Mean Absolute Percentage Error of ± 6.14%. The BitMatrix sketch was implemented using P4 language and a simulator was also developed, that allowed its scaling using real traces from CAIDA in an NSF network topology.

Vorheriger Artikel Monte Carlo Tree Search with Last-Good-Reply Policy for Cognitive Optimization of Cloud-Ready Optical Networks

Nächster Artikel Decomposition Based Cloud Resource Demand Prediction Using Extreme Learning Machines

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

https://github.com/regisftm/bitmatrix.

Equations 7, 8, 9, 10, and 11 are expressed based on the topology shown in Fig. 2 for sake of the readers. However, they can be generalized to any tenant, device, or link.

http://www.caida.org/data/passive/passive_2012_dataset.xml.

CISCO: 2020 global networking trends report. Tech. rep., CISCO (2019). https://engage2demand.cisco.com/LP=18332?ccid=cc001244&oid=rpten018612. Accessed 6 Jan 2020

Dimitropoulos, X., Hurley, P., Kind, A.: Probabilistic lossy counting: an efficient algorithm for finding heavy hitters. Comput. Commun. Rev. 38, 5 (2008)CrossRef

Moshref, M., Yu, M., Govindan, R., Vahdat, A.: Scream: sketch resource allocation for software-defined measurement. In: Proceedings of the 11th ACM conference on emerging networking experiments and technologies, CoNEXT ’15, pp. 14:1–14:13. ACM, Heidelberg (2015). https://doi.org/10.1145/2716281.2836099

Moshref, M., Yu, M.Y., Govindan, R., Vahdat, A.: DREAM: Dynamic resource allocation for software-defined measurement . Proceedings of the 2014 ACM SIGCOMM conference (2014)

Yu, M., Jose, L., Miao, R.: Software defined traffic measurement with opensketch. In: Proceedings of the 10th USENIX conference on networked systems design and implementation, NSDI’13, pp. 29–42. USENIX Association, Lombard (2013). http://dl.acm.org/citation.cfm?id=2482626.2482631

Claise, B.: Cisco systems NetFlow services export version 9. RFC 3954, Cisco Systems (2004). https://tools.ietf.org/html/rfc3954. Accessed 6 Jan 2020

sflow-rt (2019). https://sflow-rt.com/. Accessed 9 Aug 2019

Gibbons, P.B., Matias, Y.: New sampling-based summary statistics for improving approximate query answers. ACM SIGMOD Rec. (1999). https://doi.org/10.1145/276304.276334CrossRef

Demaine, E.D., López-Ortiz, A., Munro, J.I.: Frequency estimation of internet packet streams with limited space. In: Möhring, R., Raman, R. (eds.) Algorithms—ESA 2002, pp. 348–360. Springer, Berlin (2002)CrossRef

10.

Kamiyama, N., Mori, T.: Simple and accurate identification of high-rate flows by packet sampling. In: Proceedings IEEE INFOCOM 2006. In: 25TH IEEE international conference on computer communications, pp. 1–13 (2006). https://doi.org/10.1109/INFOCOM.2006.324

11.

Babcock, B., Olston, C.: Distributed top-k monitoring. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (2003). https://doi.org/10.1145/872757.872764

12.

Zhao, Q.G., Kumar, A., Wang, J., Xu, J.J.: Data streaming algorithms for accurate and efficient measurement of traffic and flow matrices. In: Proceedings of the 2005 ACM sigmetrics international conference on measurement and modeling of computer systems, SIGMETRICS ’05, pp. 350–361. ACM, Banff (2005). https://doi.org/10.1145/1064212.1064258

13.

Bandi, N., Metwally, A., Agrawal, D., El Abbadi, A.: Fast data stream algorithms using associative memories. In: Proceedings of the 2007 ACM SIGMOD international conference on management of data, SIGMOD ’07, pp. 247–256. ACM, Beijing (2007). https://doi.org/10.1145/1247480.1247510

14.

Mathew, R., Katkar, V.: Survey of low rate dos attack detection mechanisms. In: Proceedings of the international conference & 38; workshop on emerging trends in technology, ICWET ’11, pp. 955–958. ACM, Mumbai (2011). https://doi.org/10.1145/1980022.1980227

15.

Krishnamurthy, B., Sen, S., Zhang, Y., Chen, Y.: Sketch-based change detection: methods, evaluation, and applications. In: Proceedings of the 3rd ACM SIGCOMM conference on internet measurement, IMC ’03, pp. 234–247. ACM, Miami Beach (2003). https://doi.org/10.1145/948205.948236

16.

Schweller, R., Gupta, A., Parsons, E., Chen, Y.: Reversible sketches for efficient and accurate change detection over network data streams. In: Proceedings of the 4th ACM SIGCOMM conference on internet measurement, IMC ’04, pp. 207–212. ACM, Taormina (2004). https://doi.org/10.1145/1028788.1028814

17.

Duffield, N., Lund, C., Thorup, M.: Estimating flow distributions from sampled flow statistics. IEEE/ACM Trans. Netw. 13(5), 933–946 (2005). https://doi.org/10.1109/TNET.2005.852874CrossRef

18.

Kumar, A., Sung, M., Xu, J.J., Wang, J.: Data streaming algorithms for efficient and accurate estimation of flow size distribution. SIGMETRICS Perform. Eval. Rev. 32(1), 177–188 (2004). https://doi.org/10.1145/1012888.1005709CrossRef

19.

Guanyao Huang, Lall, A., Chuah, C., Jun Xu: Uncovering global icebergs in distributed monitors. In: 2009 17th international workshop on quality of service, pp. 1–9 (2009)

20.

Sanjuàs-Cuxart, J., Barlet-Ros, P., Duffield, N., Kompella, R.: Sketching the delay: tracking temporally uncorrelated flow-level latencies. Proceedings of the ACM SIGCOMM internet measurement conference, IMC (2011). https://doi.org/10.1145/2068816.2068861

21.

Zhang, Y., Singh, S., Sen, S., Duffield, N., Lund, C.: Online identification of hierarchical heavy hitters: algorithms, evaluation, and applications. In: Proceedings of the 4th ACM SIGCOMM conference on internet measurement, IMC ’04, p. 101–114. Association for Computing Machinery, New York (2004). https://doi.org/10.1145/1028788.1028802

22.

Li, X., Bian, F., Crovella, M., Diot, C., Govindan, R., Iannaccone, G., Lakhina, A.: Detection and identification of network anomalies using sketch subspaces. In: Proceedings of the 6th ACM sigcomm conference on internet measurement, IMC ’06, p. 147–152. Association for Computing Machinery, New York (2006). https://doi.org/10.1145/1177080.1177099

23.

Huang, Q., Lee, P.P.: A hybrid local and distributed sketching design for accurate and scalable heavy key detection in network data streams. Comput. Netw. 91(C), 298–315 (2015). https://doi.org/10.1016/j.comnet.2015.08.025CrossRef

24.

Cormode, G., Muthukrishnan, S.: An improved data stream summary: the count-min sketch and its applications. J. Algorithms 55(1), 58–75 (2005). https://doi.org/10.1016/j.jalgor.2003.12.001MathSciNetCrossRefMATH

25.

Estan, C., Varghese, G.: New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice. ACM Trans. Comput. Syst. 21, 270–313 (2003)CrossRef

26.

Mitzenmacher, M., Pagh, R., Pham, N.: Efficient estimation for high similarities using odd sketches. In: Proceedings of the 23rd international conference on world wide web, WWW ’14, pp. 109–118. Association for Computing Machinery, New York (2014). https://doi.org/10.1145/2566486.2568017

27.

Vieira, M.A.M., Castanho, M.S., Pacífico, R.D.G., Santos, E.R.S., Júnior, E.P.M.C., Vieira, L.F.M.: Fast packet processing with ebpf and xdp: concepts, code, challenges, and applications. ACM Comput. Surv. (2020). https://doi.org/10.1145/3371038CrossRef

28.

Pacífico, R.D.G., Silva, L.B., Coelho, G.R., Silva, P.G., Vieira, A.B., Vieira, M.A.M., Ítalo, F.S.C., Vieira, L.F.M., Nacif, J.A.M.: Bloomtime: space-efficient stateful tracking of time-dependent network performance metrics. Telecommun. Syst. (2020). https://doi.org/10.1007/s11235-020-00653-1CrossRef

29.

Li, Y., Miao, R., Kim, C., Yu, M.: Flowradar: a better netflow for data centers. In: 13th USENIX symposium on networked systems design and implementation (NSDI 16), pp. 311–324. USENIX Association, Santa Clara (2016)

30.

Bosshart, P., Daly, D., Gibb, G., Izzard, M., McKeown, N., Rexford, J., Schlesinger, C., Talayco, D., Vahdat, A., Varghese, G., Walker, D.: P4: programming protocol-independent packet processors. SIGCOMM Comput. Commun. Rev. 44(3), 87–95 (2014). https://doi.org/10.1145/2656877.2656890CrossRef

31.

Kim, C., Sivaraman, A., Katta, N., Bas, A., Dixit, A., Wobker, L.J.: In-band network telemetry via programmable dataplanes. In: Proceedings of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research, SOSR ’15. ACM, Santa Clara (2015)

32.

Sivaraman, V., Narayana, S., Rottenstreich, O., Muthukrishnan, S., Rexford, J.: Heavy-hitter detection entirely in the data plane. In: Proceedings of the symposium on SDN research, SOSR ’17, pp. 164–176. ACM, Santa Clara (2017). https://doi.org/10.1145/3050220.3063772

33.

Martins, R., Garcia, L.F., Villaça, R., Verdi, F.L.: Using probabilistic data structures for monitoring of multi-tenant p4-based networks. In: Proceedings of the IEEE symposium on computers and communications, ICC ’18. IEEE (2018). https://doi.org/10.1109/ISCC.2018.8538352

34.

Zhang, Y.: An adaptive flow counting method for anomaly detection in sdn. In: Proceedings of the 9th ACM conference on emerging networking experiments and technologies, CoNEXT ’13, pp. 25–30. ACM, Santa Barbara (2013). https://doi.org/10.1145/2535372.2535411

35.

Xie, Y., Sekar, V., Maltz, D.A., Reiter, M.K., Zhang, H.: Worm origin identification using random moonwalks. In: 2005 IEEE symposium on security and privacy (S P’05), pp. 242–256. IEEE, Oakland (2005). https://doi.org/10.1109/SP.2005.23

36.

Benson, T., Anand, A., Akella, A., Zhang, M.: Microte: fine grained traffic engineering for data centers. In: Proceedings of the seventh conference on emerging networking experiments and technologies, CoNEXT ’11, pp. 8:1–8:12. ACM, Tokyo (2011). https://doi.org/10.1145/2079296.2079304

37.

Feldmann, A., Greenberg, A., Lund, C., Reingold, N., Rexford, J., True, F.: Deriving traffic demands for operational ip networks: methodology and experience. IEEE/ACM Trans. Netw. 9(3), 265–280 (2001). https://doi.org/10.1109/90.929850CrossRef

38.

Wang, N., Ho, K., Pavlou, G., Howarth, M.: An overview of routing optimization for internet traffic engineering. Commun. Surveys Tuts. 10(1), 36–56 (2008). https://doi.org/10.1109/COMST.2008.4483669CrossRef

39.

Sivaraman, V., Narayana, S., Rottenstreich, O., Muthukrishnan, S., Rexford, J.: Heavy-hitter detection entirely in the data plane. In: Proceedings of the symposium on SDN research, SOSR ’17, p. 164–176. Association for computing machinery, New York, NY, USA (2017). https://doi.org/10.1145/3050220.3063772

40.

Kim, J., Sim, A.: A new approach to multivariate network traffic analysis. J. Comput. Sci. Technol. 34(2), 388–402 (2019). https://doi.org/10.1007/s11390-019-1915-yCrossRef

41.

Phaal, P., Panchen, A.S., McKee, N.: InMon corporation’s sFlow: a method for monitoring traffic in switched and routed networks. RFC 3176, internet engineering task force (IETF) (2001). https://tools.ietf.org/html/rfc3176

42.

Estan, C., Varghese, G.: New directions in traffic measurement and accounting. In: Proceedings of the 1st ACM SIGCOMM workshop on Internet Measurement, IMW ’01, pp. 75–80. ACM, San Francisco (2001). https://doi.org/10.1145/505202.505212

43.

Ramachandran, A., Seetharaman, S., Feamster, N., Vazirani, V.: Fast monitoring of traffic subpopulations. In: Proceedings of the 8th ACM SIGCOMM conference on internet measurement, IMC ’08, pp. 257–270. ACM, Vouliagmeni (2008). https://doi.org/10.1145/1452520.1452551

44.

Braverman, V., Liu, Z., Singh, T., Vinodchandran, N.V., Yang, L.F.: New bounds for the CLIQUE-GAP problem using graph decomposition theory. In: Mathematical Foundations of Computer Science 2015: 40th International Symposium, MFCS 2015, Milan, Italy, August 24–28, 2015, Proceedings, Part II, pp. 151–162 (2015)

45.

Lall, A., Sekar, V., Ogihara, M., Xu, J., Zhang, H.: Data streaming algorithms for estimating entropy of network traffic. SIGMETRICS Perform. Eval. Rev. 34(1), 145–156 (2006). https://doi.org/10.1145/1140103.1140295CrossRef

46.

Liu, Z., Manousis, A., Vorsanger, G., Sekar, V., Braverman, V.: One sketch to rule them all: Rethinking network flow monitoring with univmon. In: Proceedings of the 2016 ACM SIGCOMM conference, SIGCOMM ’16, pp. 101–114. ACM, Florianopolis (2016). https://doi.org/10.1145/2934872.2934906

47.

Wellem, T., Lai, Y., Huang, C., Chung, W.: A flexible sketch-based network traffic monitoring infrastructure. IEEE Access 7, 92476–92498 (2019)CrossRef

48.

Huang, Q., Jin, X., Lee, P.P.C., Li, R., Tang, L., Chen, Y.C., Zhang, G.: Sketchvisor: Robust network measurement for software packet processing. In: Proceedings of the conference of the ACM special interest group on data communication, SIGCOMM ’17, pp. 113–126. ACM, Los Angeles (2017). https://doi.org/10.1145/3098822.3098831

49.

Shahbaz, M., Choi, S., Pfaff, B., Kim, C., Feamster, N., McKeown, N., Rexford, J.: Pisces: A programmable, protocol-independent software switch. In: Proceedings of the 2016 ACM SIGCOMM conference, SIGCOMM ’16, pp. 525–538. ACM, Florianopolis (2016). https://doi.org/10.1145/2934872.2934886

50.

Dang, H.T., Canini, M., Pedone, F., Soulé, R.: Paxos made switch-y. SIGCOMM Comput. Commun. Rev. 46(2), 18–24 (2016). https://doi.org/10.1145/2935634.2935638CrossRef

51.

Sivaraman, A., Kim, C., Krishnamoorthy, R., Dixit, A., Budiu, M.: Dc.p4: Programming the forwarding plane of a data-center switch. In: Proceedings of the 1st ACM SIGCOMM symposium on software defined networking research, SOSR ’15, pp. 2:1–2:8. ACM, Santa Clara (2015). https://doi.org/10.1145/2774993.2775007

52.

Snoeren, A.C., Partridge, C., Sanchez, L.A., Jones, C.E., Tchakountio, F., Kent, S.T., Strayer, W.T.: Hash-based ip traceback. SIGCOMM Comput. Commun. Rev. 31(4), 3–14 (2001). https://doi.org/10.1145/964723.383060CrossRef

53.

NETRONOME: Netronome Agilio SmartNIC. https://www.netronome.com/products/agilio-cx/ (2020). Accessed 18 Mar 2020

54.

Yang, T., Jiang, J., Liu, P., Huang, Q., Gong, J., Zhou, Y., Miao, R., Li, X., Uhlig, S.: Elastic sketch: adaptive and fast network-wide measurements. In: Proceedings of the 2018 ACM SIGCOMM conference, SIGCOMM ’18. ACM (2018)

55.

Tableau: Tableau Software. https://www.tableau.com/ (2020). Accessed 02 May 2020

56.

Martins, R.: Packet routing analyses using probabilistic data structures in Multi-Tenant Networks based on programmable devices. Master Thesis. Federal University of Sāo Carlos, UFSCar (2018). https://repositorio.ufscar.br/handle/ufscar/11892

Titel: BitMatrix: A Multipurpose Sketch for Monitoring of Multi-tenant Networks
verfasst von: Regis Francisco Teles Martins
Rodolfo da Silva Villaça
Fábio Luciano Verdi
Publikationsdatum: 30.07.2020
Verlag: Springer US
Erschienen in: Journal of Network and Systems Management / Ausgabe 4/2020
Print ISSN: 1064-7570
Elektronische ISSN: 1573-7705
DOI: https://doi.org/10.1007/s10922-020-09556-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2020

Expand or Oversize? Planning Internet Access Network in a Demand Growth Scenario

ISDSDN: Mitigating SYN Flood Attacks in Software Defined Networks

Fuzzy, Dynamic and Trust Based Routing Protocol for IoT

ORCHESTRA: Supercharging Wireless Backhaul Networks Through Multi-technology Management

Decomposition Based Cloud Resource Demand Prediction Using Extreme Learning Machines

Preemptive Resource Provisioning for Container-Based Audio/Video Encrypted Collaboration Applications