FCM-Sketch: Generic Network Measurements with Data Plane Support - Research Overview

Aug 20, 2026

Sketches enable accurate, fine-grained network measurements essential for management tasks such as flow size estimation and heavy-hitter detection. Count-Min (CM) sketches are widely adopted but suffer from poor accuracy and limited generality when used on high-speed programmable switches. FCM proposes a framework for generic measurements with high accuracy, centered on FCM-Sketch, a lightweight data-plane data structure implementable on PISA programmable switches using P4. Experiments on a Barefoot Tofino switch show 50%–80% error reduction versus CM-sketch and other state-of-the-art methods across multiple measurement tasks.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages15

Reading Time38 min

AccessFree to download

Abstract

Introduction

Network measurement requirements

Software limits at high speeds

Count-Min sketch and accuracy challenges

Data-plane programmability and generic measurement gaps

Proposed framework: FCM

Data-plane: FCM-Sketch

Control-plane: CPU/DRAM assisted tasks

FCM-Sketch: Generic Network Measurements with Data Plane Support Cha Hwan Song, Pravein Govindan Kannan, Bryan Kian Hsiang Low, Mun Choon Chan {songch,pravein,lowkh, [chanmc}@comp.nus.edu.sg](chanmc}@comp.nus.edu.sg) School of Computing, National University of Singapore ABSTRACT Sketches have successfully provided accurate and fine-grained measurements (e.g., flow size and heavy hitters) which are imperative for network management. In particular, Count-Min (CM) sketch is widely utilized in many applications due to its simple design and ease of implementation. There have been many efforts to build monitoring frameworks based on Count-Min sketch. However, these frameworks either support very specific measurement tasks or they cannot be implemented on high-speed programmable hardware (PISA) . In this work, we propose FCM, a framework that is designed to support generic network measurement with high accuracy. Our key contribution is FCM-Sketch, a data structure that has a lightweight implementation on the emerging PISA programmable switches. FCM-Sketch can also be used as a substitute for CM-Sketch in applications that use CM-Sketch. We have implemented FCM-Sketch on a commodity programmable switch (Barefoot Tofino) using the P4 language. Our evaluation shows that FCM-Sketch can reduce the errors in many measurement tasks by 50% to 80% compared to CM-Sketch and other state-of-the-art approaches. CCS CONCEPTS • Networks → Network measurement; Programmable networks. KEYWORDS Streaming Algorithm, Sketches, Network Measurement, Generic, Data Plane, Programmable Switch, PISA, P4 ACM Reference Format: Cha Hwan Song, Pravein Govindan Kannan, Bryan Kian Hsiang Low, Mun Choon Chan. 2020. FCM-Sketch: Generic Network Measurements with Data Plane Support. In The 16th International Conference on emerging Networking EXperiments and Technologies (CoNEXT’20), December 1–4, 2020, Barcelona, Spain. ACM, New York, NY, USA, 15 pages. [https://doi.org/10.1145/3386367](https://doi.org/10.1145/3386367) . 3432729 1 INTRODUCTION Network measurement is indispensable for efficient network management such as load balancing, congestion control, quality of Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission [and/or a fee. Request permissions from permissions@acm.org](and/or a fee. Request permissions from permissions@acm.org). CoNEXT’20, December 1–4, 2020, Barcelona, Spain © 2020 Copyright held by the owner/author(s) . Publication rights licensed to ACM. ACM ISBN 978-1-4503-7948-9/20/12. . . $15.00 [https://doi.org/10.1145/3386367.3432729](https://doi.org/10.1145/3386367.3432729) service, scheduling, and anomaly detection [13, 46, 47, 50, 57, 63] . To assist in-network management, fine-grained measurements such as per-flow size [22], heavy hitter detection [54], cardinality [58], etc. are needed. With the abundance of memory and availability of parallel processing (e.g., SIMD and multi-core), software switches have been used as platforms for network measurement [31, 51, 62] . However, with network link speeds reaching 400 Gbps and switching capacity exceeding tens ofTbps [1], it is challenging for software processing speed to scale accordingly [43]. Techniques like sampling (e.g., NetFlow [3]) are often utilized to reduce measurement overhead. However, it cannot provide accurate and fine-grained statistics. Often, there is an inevitable loss in measurement resolution and accuracy if network monitoring is performed solely in software without hardware (data

FAQs

What problem does FCM target in network measurement frameworks?

FCM targets the need for high-resolution, generic measurement that scales with switch throughput while maintaining accuracy when implemented in the data plane.

How does FCM-Sketch relate to Count-Min (CM) sketch?

FCM-Sketch is designed as a better Count-Min sketch, with a lightweight implementation in the switch data plane and the ability to replace CM-Sketch in systems that rely on data-plane queries.

What hardware and implementation method is used to evaluate FCM-Sketch?

FCM-Sketch is implemented on a commodity programmable switch (Barefoot Tofino) using the P4 language, and evaluated against CM-Sketch and other approaches.

Aug 20, 2026

Upload by Aria Callaghan