Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
PPS: A Low-Latency and Low-Complexity Switching Architecture Based on Packet Prefetch and Arbitration Prediction Kapitel lesen Erstes Kapitel lesen

2020 | OriginalPaper | Buchkapitel

HBL-Sketch: A New Three-Tier Sketch for Accurate Network Measurement

verfasst von : Keyan Zhao, Junxiao Wang, Heng Qi, Xin Xie, Xiaobo Zhou, Keqiu Li

Erschienen in: Algorithms and Architectures for Parallel Processing

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

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 benefits: high computation efficiency and acceptable error rate. However, there is usually a tradeoff between accuracy and memory cost. To make a reasonable tradeoff, we propose a novel sketch, namely the HBL (Heavy-Buffer-Light) sketch in this paper. The architecture of HBL sketch is three-tier consisting of heavy part, buffer layer and light part, which can be viewed as an improved version of Elastic sketch which is the state-of-the-art in network measurement. Compared to the Elastic sketch and other typical work, HBL sketch can reduce the average relative error rate by 55%–93% with the same memory capacity limitations.

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
Vorheriges Kapitel Flexible Data Flow Architecture for Embedded Hardware Accelerators
Nächstes Kapitel Accelerating Large Integer Multiplication Using Intel AVX-512IFMA
Fußnoten
Literatur
1.
2.
3.
AlGhadhban, A., Shihada, B.: Flight: a fast and lightweight elephant-flow detection mechanism. In: 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS), pp. 1537–1538. IEEE (2018)
4.
Alipourfard, O., Moshref, M., Zhou, Y., Yang, T., Yu, M.: A comparison of performance and accuracy of measurement algorithms in software. In: Proceedings of the Symposium on SDN Research, p. 18. ACM (2018)
5.
Ben Basat, R., Einziger, G., Friedman, R., Luizelli, M.C., Waisbard, E.: Constant time updates in hierarchical heavy hitters. In: Proceedings of the Conference of the ACM Special Interest Group on Data Communication, pp. 127–140. ACM (2017)
6.
Bloom, B.H.: Space/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422–426 (1970)CrossRef
7.
Brauckhoff, D., Tellenbach, B., Wagner, A., May, M., Lakhina, A.: Impact of packet sampling on anomaly detection metrics. In: Proceedings of the 6th ACM SIGCOMM Conference on Internet Measurement, pp. 159–164. ACM (2006)
8.
9.
Cormode, G., Muthukrishnan, S.: An improved data stream summary: the count-min sketch and its applications. J. Algorithms 55(1), 58–75 (2005)MathSciNetCrossRef
10.
Črepinšek, M., Liu, S.H., Mernik, M.: Exploration and exploitation in evolutionary algorithms: a survey. ACM Comput. Surv. 45(3), 35–68 (2013)CrossRef
11.
Estan, C., Varghese, G.: New directions in traffic measurement and accounting. ACM SIGCOMM Comput. Commun. Rev. 32, 323–336 (2002) CrossRef
12.
Flajolet, P., Martin, G.N.: Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci. 31(2), 182–209 (1985)MathSciNetCrossRef
13.
Gong, J., et al.: HeavyKeeper: an accurate algorithm for finding top-k elephant flows. In: 2018 USENIX Annual Technical Conference (USENIX ATC 2018), pp. 909–921 (2018)
14.
Huang, Q., et al.: SketchVisor: robust network measurement for software packet processing. In: Proceedings of the Conference of the ACM Special Interest Group on Data Communication, pp. 113–126. ACM (2017)
15.
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 2016), pp. 311–324 (2016)
16.
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, pp. 101–114. ACM (2016)
17.
Liu, Z., Gao, D., Liu, Y., Zhang, H., Foh, C.H.: An adaptive approach for elephant flow detection with the rapidly changing traffic in data center network. Int. J. Network Manage. 27(6), e1987 (2017)CrossRef
18.
Mai, J., Chuah, C.N., Sridharan, A., Ye, T., Zang, H.: Is sampled data sufficient for anomaly detection? In: Proceedings of the 6th ACM SIGCOMM Conference on Internet Measurement, pp. 165–176. ACM (2006)
19.
Poupart, P., et al.: Online flow size prediction for improved network routing. In: 2016 IEEE 24th International Conference on Network Protocols (ICNP), pp. 1–6. IEEE (2016)
20.
Przybylski, S., Horowitz, M., Hennessy, J.: Characteristics of performance-optimal multi-level cache hierarchies. In: The 16th Annual International Symposium on Computer Architecture, pp. 114–121. IEEE (1989)
21.
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, pp. 164–176. ACM (2017)
22.
Wang, M., Li, B., Li, Z.: sFlow: towards resource-efficient and agile service federation in service overlay networks. In: Proceedings of the 24th International Conference on Distributed Computing Systems, pp. 628–635. IEEE (2004)
23.
Wellem, T., Lai, Y.K., Chung, W.Y.: A software defined sketch system for traffic monitoring. In: Proceedings of the Eleventh ACM/IEEE Symposium on Architectures for Networking and Communications Systems, pp. 197–198. IEEE Computer Society (2015)
24.
Wellem, T., Lai, Y.K., Huang, C.Y., Chung, W.Y.: A hardware-accelerated infrastructure for flexible sketch-based network traffic monitoring. In: 2016 IEEE 17th International Conference on High Performance Switching and Routing (HPSR), pp. 162–167. IEEE (2016)
25.
Yang, T., et al.: Elastic sketch: adaptive and fast network-wide measurements. In: Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication, pp. 561–575. ACM (2018)
26.
Yang, T., et al.: Sf-sketch: a fast, accurate, and memory efficient data structure to store frequencies of data items. In: 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pp. 103–106. IEEE (2017)
27.
Yang, T., et al.: Empowering sketches with machine learning for network measurements. In: Proceedings of the 2018 Workshop on Network Meets AI & ML, pp. 15–20. ACM (2018)
28.
Zhou, A., Zhu, H., Liu, L., Zhu, C.: Identification of heavy hitters for network data streams with probabilistic sketch. In: 2018 IEEE 3rd International Conference on Cloud Computing and Big Data Analysis (ICCCBDA), pp. 451–456. IEEE (2018)
29.
Zhou, Y., Jin, H., Liu, P., Zhang, H., Yang, T., Li, X.: Accurate per-flow measurement with bloom sketch. In: IEEE INFOCOM 2018-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 1–2. IEEE (2018)
30.
Zhou, Y., Liu, P., Jin, H., Yang, T., Dang, S., Li, X.: One memory access sketch: a more accurate and faster sketch for per-flow measurement. In: GLOBECOM 2017–2017 IEEE Global Communications Conference, pp. 1–6. IEEE (2017)
Metadaten
Titel
HBL-Sketch: A New Three-Tier Sketch for Accurate Network Measurement
verfasst von
Keyan Zhao
Junxiao Wang
Heng Qi
Xin Xie
Xiaobo Zhou
Keqiu Li
Copyright-Jahr
2020
Buch
Algorithms and Architectures for Parallel Processing

Print ISBN: 978-3-030-38990-1

Electronic ISBN: 978-3-030-38991-8

Copyright-Jahr: 2020

DOI
https://doi.org/10.1007/978-3-030-38991-8_4