Top

Published in:

10-02-2020

BloomTime: space-efficient stateful tracking of time-dependent network performance metrics

Authors: Racyus D. G. Pacífico, Lucas B. Silva, Gerferson R. Coelho, Pablo G. Silva, Alex B. Vieira, Marcos A. M. Vieira, Ítalo F. S. Cunha, Luiz F. M. Vieira, José A. M. Nacif

Published in: Telecommunication Systems | Issue 2/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Network monitoring is essential to tasks ranging from planning to troubleshooting. Unfortunately, comprehensive real-time monitoring of complex networks with large traffic volume is challenging. In particular, tracking of time-dependent metrics, such as round-trip latency or transmission rate requires maintaining state and this is hard to scale. We propose BloomTime: a network monitoring primitive in hardware that employs standard bloom filters to approximately track the times between packets. We have prototyped BloomTime on the NetFPGA platform. As a use case, we use BloomTime to monitor the mean and variance of packet inter-arrival times. We have compared BloomTime against end-host measurements and a centralized solution using classic stateful monitoring. We show that BloomTime can monitor 70 times more flows than the traditional stateful approach with approximation errors below 20%. BloomTime was validated in a realistic test environment using real traces. We show that BloomTime can monitor simultaneously 2000 flows on the NetFPGA 1G board (first generation) with 4 MB of SRAM.

previous article Large-scale channel characterization at 28 GHz on a university campus in the United Arab Emirates

next article Nature-inspired optimization algorithms for community detection in complex networks: a review and future trends

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Programmable Forwarding Engine.

A 5-tuple flow definition computes hash functions over the (source address, destination address, source port, destination port, and protocol identifier) IP header fields.

We assume that both forward and reverse paths traverse BloomTime.

The hash function for outgoing packets exchanges position of IP addresses and ICMP code, while the hash function for incoming packets does not.

The NetFPGA SRAM is addressable only per line. When marking just a bit corresponding to \(B_0\), our prototype needs to read the entire line and write it back. Other architectures might allow for write-only implementations.

Available in: http://www.tcpdump.org/.

Available in: https://sourceforge.net/projects/libnet/.

Available in: http://bittwist.sourceforge.net.

Available in: https://dpkt.readthedocs.io/.

1G, N. (2017). Quad-port gigabit nic. http://netfpga.org/site/#/systems/4netfpga-1g/applications/ . Retrieved 08 August 2017.

Al-Fares, M., Radhakrishnan, S., Raghavan, B., Huang, N., & Vahdat, A. (2010). Hedera: Dynamic flow scheduling for data center networks. In Proceedings of the 7th USENIX conference on networked systems design and implementation, NSDI’10 (pp. 19–19). USENIX Association, Berkeley, CA, USA. http://dl.acm.org/citation.cfm?id=1855711.1855730.

Anwer, B., Benson, T., Feamster, N., Levin, D., & Rexford, J. (2013). A slick control plane for network middleboxes. In Proceedings of the second ACM SIGCOMM workshop on hot topics in software defined networking (pp. 147–148). ACM.

Bender, M. A., Farach-Colton, M., Johnson, R., Kraner, R., Kuszmaul, B. C., Medjedovic, D., et al. (2012). Don’t thrash: How to cache your hash on flash. Proceedings of the VLDB Endowment, 5(11), 1627–1637. https://doi.org/10.14778/2350229.2350275.CrossRef

Benson, T., Anand, A., Akella, A., & Zhang, M. (2011). Microte: Fine grained traffic engineering for data centers. In Proceedings of the seventh conference on emerging networking experiments and technologies (p. 8). ACM.

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

Bonomi, F., Mitzenmacher, M., Panigrah, R., Singh, S., & Varghese, G. (2006). Beyond bloom filters: From approximate membership checks to approximate state machines. In ACM SIGCOMM computer communication review (Vol. 36, pp. 315–326). ACM.

Bonomi, F., Mitzenmacher, M., Panigrahy, R., Singh, S., & Varghese, G. (2006). An improved construction for counting bloom filters. In European Symposium on algorithms (pp. 684–695). Springer

Borthakur, D. (2007). The hadoop distributed file system: Architecture and design. Hadoop Project Website, 11(2007), 21.

10.

Broder, A., & Mitzenmacher, M. (2004). Network applications of bloom filters: A survey. Internet Mathematics, 1(4), 485–509.CrossRef

11.

Byers, J., Considine, J., Mitzenmacher, M., & Rost, S. (2002). Informed content delivery across adaptive overlay networks. SIGCOMM Computer Communivation Review, 32(4), 47–60. https://doi.org/10.1145/964725.633031.CrossRef

12.

Cai, H., Ge, P., & Wang, J. (2008) Applications of bloom filters in peer-to-peer systems: Issues and questions. In International conference on networking, architecture, and storage, NAS’08 (pp. 97–103). IEEE.

13.

Chang, F., Dean, J., Ghemawat, S., Hsieh, W. C., Wallach, D. A., Burrows, M., et al. (2008). Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems, 26(2), 4:1–4:26. https://doi.org/10.1145/1365815.1365816.CrossRef

14.

Chen, X., Feibish, S.L., Koral, Y., Rexford, J., Rottenstreich, O., Monetti, S.A., & Wang, T.Y. (2019). Fine-grained queue measurement in the data plane. In Proceedings of the 15th international conference on emerging networking experiments and technologies, CoNEXT ’19 (pp. 15–29). ACM, New York, NY, USA . https://doi.org/10.1145/3359989.3365408.

15.

Chen, Y., Farley, T., & Ye, N. (2004). Qos requirements of network applications on the internet. Information Knowledge Systems Management, 4(1), 55–76.

16.

Chowdhury, S.R., Bari, M.F., Ahmed, R., & Boutaba, R. (2014) Payless: A low cost network monitoring framework for software defined networks. In Network operations and management symposium (NOMS) (pp. 1–9). IEEE.

17.

Curtis, A. R., Mogul, J. C., Tourrilhes, J., Yalagandula, P., Sharma, P., & Banerjee, S. (2011). Devoflow: Scaling flow management for high-performance networks. ACM SIGCOMM Computer Communication Review, 41(4), 254–265.CrossRef

18.

Daniel, E.J., White, C.M., Teague, K., et al. (2003). An interarrival delay jitter model using multistructure network delay characteristics for packet networks. In The thirty-seventh asilomar conference on signals, systems and computers (Vol. 2, pp. 1738–1742). IEEE.

19.

Deri, L. (2007). High-speed dynamic packet filtering. Journal of Network and Systems Management, 15(3), 401–415.CrossRef

20.

Dharmapurikar, S., Krishnamurthy, P., Sproull, T., & Lockwood, J. (2003). Deep packet inspection using parallel bloom filters. In 11th symposium on high performance interconnects, 2003. Proceedings (pp. 44–51). IEEE.

21.

Dharmapurikar, S., Krishnamurthy, P., & Taylor, D. E. (2006). Longest prefix matching using bloom filters. IEEE/ACM Transactions on Networking, 14(2), 397–409.CrossRef

22.

Fan, L., Cao, P., Almeida, J., & Broder, A. Z. (2000). Summary cache: A scalable wide-area web cache sharing protocol. IEEE/ACM Transactions on Networking, 8(3), 281–293. https://doi.org/10.1109/90.851975.CrossRef

23.

Feng, Wc, Shin, K. G., Kandlur, D. D., & Saha, D. (2002). The blue active queue management algorithms. IEEE/ACM Transactions on Networking, 10(4), 513–528. https://doi.org/10.1109/TNET.2002.801399.CrossRef

24.

Finamore, A., Mellia, M., Meo, M., Munafo, M. M., Di Torino, P., & Rossi, D. (2011). Experiences of internet traffic monitoring with tstat. IEEE Network, 25(3), 8–14.CrossRef

25.

Gangam, S., Chandrashekar, J., Cunha, Í., & Kurose, J. (2013). Estimating tcp latency approximately with passive measurements. In International conference on passive and active network measurement (pp. 83–93). Springer.

26.

Gupta, A., Harrison, R., Canini, M., Feamster, N., Rexford, J., & Willinger, W. (2018). Sonata: Query-driven streaming network telemetry. In Proceedings of the 2018 conference of the ACM special interest group on data communication, SIGCOMM ’18 (pp. 357–371). ACM, New York, NY, USA. https://doi.org/10.1145/3230543.3230555.

27.

Khandelwal, A., Agarwal, R., & Stoica, I. (2019). Confluo: Distributed monitoring and diagnosis stack for high-speed networks. In: NSDI (pp. 421–436).

28.

Li, G., Zhang, M., Liu, C., Kong, X., Chen, A., Gu, G., & Duan, H. (2019) Nethcf: Enabling line-rate and adaptive spoofed ip traffic filtering. In 2019 IEEE 27th international conference on network protocols (ICNP) (pp. 1–12). IEEE.

29.

Moshref, M., Yu, M., & Govindan, R. (2013). Resource/accuracy tradeoffs in software-defined measurement. In Proceedings of the second ACM SIGCOMM workshop on hot topics in software defined networking (pp. 73–78). ACM.

30.

Narayan, A., Cangialosi, F., Goyal, P., Narayana, S., Alizadeh, M., & Balakrishnan, H. (2017). The case for moving congestion control out of the datapath. In Proceedings of the 16th ACM workshop on hot topics in networks, HotNets-XVI (pp. 101–107). ACM, New York, NY, USA. https://doi.org/10.1145/3152434.3152438.

31.

Narayana, S., Sivaraman, A., Nathan, V., Goyal, P., Arun, V., Alizadeh, M., Jeyakumar, V., & Kim, C. (2017). Language-directed hardware design for network performance monitoring. In Proceedings of the conference of the ACM special interest group on data communication, SIGCOMM ’17 (pp. 85–98). ACM, New York, NY, USA. https://doi.org/10.1145/3098822.3098829.

32.

NetFPGA (2015) Project switch openflow netfpga. http://github.com/NetFPGA/netfpga/wiki/OpenFlowNetFPGA100. Retrieved 22 November 2015.

33.

NetFPGA (2016). Site netfpga. http://netfpga.org. Retreived 22 August 2016.

34.

Pacífico, R., Silva, P., Cunha, I., Vieira, M., Vieira, A. B., Guedes, D., et al. (2016). Medição de desempenho de rede em hardware. XXXIV Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos - SBRC, 2016

35.

Pacífico, R., Silva, P., Vieira, A.B., Vieira, M.A.M., & Miranda Nacif, J.A. (2016). Hardware modules for packet interarrival time monitoring for software defined measurements. In 41st annual IEEE conference on local computer networks - LCN 2016.

36.

Pouwelse, J. A., Garbacki, P., Wang, J., Bakker, A., Yang, J., Iosup, A., et al. (2008). Tribler: A social-based peer-to-peer system. Concurrency and Computation: Practice and Experience, 20(2), 127–138.CrossRef

37.

Putze, F., Sanders, P., & Singler, J. (2010). Cache-, hash-, and space-efficient bloom filters. Journal of Experimental Algorithmics, 14, 4:4.4–4:4.18. https://doi.org/10.1145/1498698.1594230.CrossRef

38.

Qazi, Z. A., Tu, C. C., Chiang, L., Miao, R., Sekar, V., & Yu, M. (2013). Simple-fying middlebox policy enforcement using sdn. ACM SIGCOMM Computer Communication Review, 43(4), 27–38.CrossRef

39.

Raumer, D., Schwaighofer, L., & Carle, G. (2014). Monsamp: A distributed sdn application for qos monitoring. In 2014 federated conference on computer science and information systems (FedCSIS) (pp. 961–968). IEEE.

40.

Reynolds, P., & Vahdat, A. (2003). Efficient peer-to-peer keyword searching. In Proceedings of the ACM/IFIP/USENIX 2003 international conference on Middleware, Middleware ’03 (pp. 21–40). Springer-Verlag New York, Inc., New York, NY, USA. http://dl.acm.org/citation.cfm?id=1515915.1515918.

41.

Snoeren, A. C., Partridge, C., Sanchez, L. A., Jones, C. E., Tchakountio, F., Schwartz, B., et al. (2002). Single-packet ip traceback. IEEE/ACM Transactions on Networking (ToN), 10(6), 721–734.CrossRef

42.

Sonchack, J., Aviv, A.J., Keller, E., & Smith, J.M. (2018) Turboflow: Information rich flow record generation on commodity switches. In Proceedings of the thirteenth EuroSys conference, EuroSys ’18 (pp. 11:1–11:16). ACM, New York, NY, USA. https://doi.org/10.1145/3190508.3190558.

43.

Song, H., Dharmapurikar, S., Turner, J., & Lockwood, J. (2005). Fast hash table lookup using extended bloom filter: An aid to network processing. In Proceedings of the 2005 conference on applications, technologies, architectures, and protocols for computer communications, SIGCOMM ’05 (pp. 181–192). ACM, New York, NY, USA. https://doi.org/10.1145/1080091.1080114.

44.

Soule, A., Salamatia, K., Taft, N., Emilion, R., & Papagiannaki, K. (2004). Flow classification by histograms: Or how to go on safari in the internet. In Proceedings of the joint international conference on measurement and modeling of computer systems, SIGMETRICS ’04/Performance ’04 (pp. 49–60). ACM, New York, NY, USA. https://doi.org/10.1145/1005686.1005696.

45.

SUME, N. (2015). Netfpga sume. http://netfpga.org/site/#/systems/1netfpga-sume/details/. Retreived 27 December 2015.

46.

Tang, L., Huang, Q., & Lee, P.P. (2019). A fast and compact invertible sketch for network-wide heavy flow detection. arXiv preprint arXiv:1910.10441

47.

Van Adrichem, N.L., Doerr, C., & Kuipers, F., et al. (2014). Opennetmon: Network monitoring in openflow software-defined networks. In Network operations and management symposium (NOMS) (pp. 1–8). IEEE.

48.

Yu, M., Fabrikant, A., & Rexford, J. (2009) Buffalo: Bloom filter forwarding architecture for large organizations. In Proceedings of the 5th international conference on emerging networking experiments and technologies (pp. 313–324). ACM.

49.

Yu, M., Jose, L., & Miao, R. (2013). Software defined traffic measurement with opensketch. Symposium on Networked Systems Design and Implementation - NSDI (Vol. 13, pp. 29–42).

Title: BloomTime: space-efficient stateful tracking of time-dependent network performance metrics
Authors: Racyus D. G. Pacífico
Lucas B. Silva
Gerferson R. Coelho
Pablo G. Silva
Alex B. Vieira
Marcos A. M. Vieira
Ítalo F. S. Cunha
Luiz F. M. Vieira
José A. M. Nacif
Publication date: 10-02-2020
Publisher: Springer US
Published in: Telecommunication Systems / Issue 2/2020
Print ISSN: 1018-4864
Electronic ISSN: 1572-9451
DOI: https://doi.org/10.1007/s11235-020-00653-1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2020

Supervised classification for dynamic CoAP mode selection in real time wireless IoT networks

Large-scale channel characterization at 28 GHz on a university campus in the United Arab Emirates

UAVs-based antenna arrays using time modulation

Nature-inspired optimization algorithms for community detection in complex networks: a review and future trends

Energy-efficient RRH-association and resource allocation in D2D enabled multi-tier 5G C-RAN

Single tag scheme for segment routing in software-defined network