Pith. sign in

REVIEW 4 major objections 6 minor 27 references

PSketch: A Priority-Aware Sketch Architecture for Real-Time Flow Monitoring via eBPF

T0 review · 4 major / 6 minor · reviewed 2026-08-04 · deepseek-v4-flash

Pith's one-line read PSketch claims the first in-kernel, priority-aware sketch monitor: exact for chosen flows, approximate for everything else.

desk verdict A plausible eBPF sketch integration with real code, but the headline 'lossless priority' claim is only tested under an oracle precondition and the accuracy metrics are under-specified. read the letter →

arxiv 2509.07338 v1 pith:OL5HKFY2 submitted 2025-09-09 cs.ET

classification cs.ET
keywords eBPFpriority-awaremonitoringsketchdatastructuresin-kerneltelemetryTCPretransmissiontop-kelephantflowsCount-Minflow
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

PSketch claims to be the first priority-aware flow-monitoring framework that runs entirely inside the Linux kernel using eBPF, so it needs no programmable switch hardware. It keeps an exact hash table for a small set of high-priority flows while routing all other traffic through a sketch pipeline that estimates top-k elephant flows, per-flow packet counts, retransmission counts, and total flow cardinality. On 10 Gbps backbone traces it reports about 96% top-k detection accuracy, 100% packet recall for priority flows, above 96% retransmission recall, and throughput loss below 1.1%. If these numbers hold, PSketch offers operators a cheap, deployable way to combine lossless monitoring of critical flows with approximate visibility of the rest.

What carries the argument

The central machinery is a two-path packet classifier. The priority path is a BPF_HASH table keyed by flow 5-tuples, giving O(1) exact accounting. The approximate path is a sketch pipe: a fixed heavy-flow BPF_ARRAY whose Jenkins-hashed slots hold per-flow counters and a negative_counter; when negative_counter times VOTE_THRE reaches the slot's packet_count, the resident flow is evicted and its stats are forwarded to the sketch layers. A linear counter (m-bit array with the -m ln(V/m) estimator) estimates distinct flows, and a three-layer Count-Min sketch (three BPF arrays of 500 entries) accumulates packet and retransmission counts; reconstruction takes the minimum of the three CMS counters

What would settle it

Replay a trace with the priority table left empty and compare ground-truth packet recall for the flows the experiment would otherwise designate as priority; if those flows are still counted exactly, the pre-installation assumption is unnecessary, and if they are not, the headline priority guarantee depends on controller knowledge.

Watch

Extended reading notes

Core claim

The paper argues that priority-aware monitoring can live entirely in the kernel by splitting traffic into two paths. A hash-based priority table matches each packet's 5-tuple against installed high-priority flow keys; matched flows are counted exactly, with TCP retransmissions detected by comparing sequence numbers under a 3 ms timestamp threshold. Everything else goes through a sketch pipe: a heavy-flow table with a voting eviction rule, a linear counter for cardinality, and a three-layer Count-Min sketch that also tracks retransmission counts; a kick flag and min-of-three reconstruction reassemble statistics for flows evicted from the heavy table. Evaluation on 10 Gbps backbone traces repo

Load-bearing premise

The lossless-priority result holds only if the exact five-tuples of priority flows are installed in the priority table before those flows send packets; live traffic with no such pre-installed list bypasses the exact path.

Editorial extensions

If this is right

  • Any Linux 5.4+ host can offer priority-aware and top-k flow telemetry without programmable switches, moving monitoring from core switches to hosts and virtual machines.
  • Operators can configure exact accounting for a few critical flows (for example, distributed-training jobs) while keeping approximate visibility over all remaining traffic at under 1.1% throughput cost.
  • Retransmission telemetry becomes available per priority flow and per top-k flow from the same packet path, providing a congestion signal without separate middleboxes.
  • The reported recall numbers establish a concrete accuracy baseline for comparing future in-kernel sketch designs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the priority mechanism is a policy hook, not a detector; a natural extension is to auto-promote flows that the sketch path flags as growing, turning the system into a closed loop.
  • Editorial inference: the 3 ms retransmission threshold is effectively a reordering-versus-loss classifier, and its behavior under delay spikes or multipath reordering is untested—the likeliest place the reported recall could degrade outside the trace workload.
  • Editorial inference: the same split—exact table for a chosen subset, sketch for the rest—could apply to other kernel-level count streams such as syscalls, storage I/O, or container traffic where a few keys deserve lossless accounting.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

Summary. PSketch proposes an eBPF-based in-kernel flow-monitoring architecture that combines an exact BPF_HASH priority table with a sketch pipeline (heavy-flow table, linear counter, and a 3-layer Count-Min Sketch) for top-k and retransmission telemetry. The paper claims lossless tracking of high-priority flows, 96.0% top-k detection accuracy, 96.4% retransmission recall, and only 0.7% throughput degradation on replayed CAIDA 2019 traces at 10 Gbps. The evaluation is carried out on FABRIC testbed VMs with tcpreplay and uses Wireshark/Tshark-derived ground truth.

Significance. If the claims are substantiated, PSketch would be a practically useful step toward in-kernel flow monitoring without programmable-switch hardware. The hybrid design is intuitive, the use of commodity Linux eBPF is realistic, and the paper makes an effort to release code and evaluate on real CAIDA traces, which are commendable. However, the main quantitative claims are currently under-supported: the top-k accuracy metric is not precisely defined, the priority-flow evaluation is conducted under an oracle precondition, and the retransmission detector is a simplified heuristic with no sensitivity analysis. The architecture is plausible, but the evidence as presented does not yet establish the abstract's headline numbers.

major comments (4)
  1. [§V.B, Table 1] The headline metric "Top-k Flow Detection Accuracy" is never defined. The text only says it "measures how accurately PSketch identifies the top-k elephant flows by packet volume compared to ground truth." A reader cannot tell whether 96% is the fraction of ground-truth top-k flows present in PSketch's output, the precision of reported flows, a rank-based Jaccard similarity, or something else. Since this is the central quantitative claim, the metric must be specified precisely, and because the paper says experiments were run 10 times, Table 1 should report variance or confidence intervals rather than only point estimates.
  2. [§III.A, §V.A] The "lossless tracking of high-priority flows" claim is only tested under an oracle: the controller installs the 10 priority 5-tuples in the BPF_HASH map before tcpreplay begins, and the flows are selected from ground-truth heavy flows. The paper itself notes the "major challenge" of obtaining five-tuples in advance and proposes a gRPC confirmation mechanism, but no experiment exercises flows that arrive before or during controller insertion. Consequently, the reported 100% priority packet recall is an upper bound for the favorable case and does not support the general lossless claim. Please either scope the claim to flows whose tuples are installed before the first packet, add a dynamic-insertion experiment (e.g., install tuples after a fraction of the flow's packets have been processed), or quantify the insertion-latency budget needed to preserve losslessness.
  3. [§III.B, Algorithm 1] The retransmission detector does not maintain a true next-expected-sequence-number state: it overwrites entry.exp_seq with the current packet's sequence number (the pseudocode uses the undefined p.exp_seq) instead of advancing by payload length, and it does not model ACKs, out-of-order segments, or loss. The only guard against TCP reordering is the hand-set 3 ms timestamp threshold, for which no sensitivity analysis is given. The reported 90–96% retransmission recall is therefore not well grounded. The evaluation should compare the heuristic against ground truth under controlled reordering and loss, or the claims should be limited to "sequence-decrease events" rather than retransmissions.
  4. [§III.B–III.E, Algorithm 1] The collision/eviction and flow-reconstruction mechanism is underspecified and internally unclear. When a slot in the heavy-flow table is replaced, the evicted flow's 5-tuple is overwritten and no separate key list is maintained; the CMS stores only per-bucket counters, not flow keys. Thus the described reconstruction ("if kick_flag is set to 1, recompute the CMS indices ... take the minimum ... merged with values in the heavy flow table") cannot recover statistics for a flow that has already been evicted, because its key is gone. In Algorithm 1, the CMS update branch after setting kicked references "old stats," but those old statistics are not defined at that point. This makes the top-k per-flow packet-count recall numbers difficult to interpret.
minor comments (6)
  1. [Abstract and §I] Typographical errors: "degration" should be "degradation" in the abstract; "statics" appears where "statistics" is intended.
  2. [§III.A] The sentence "In the camera-ready version, we will clarify the original rationale of our controller module..." is not appropriate for a submitted manuscript; either provide that clarification now or remove the sentence.
  3. [§V.A] Trace details are incomplete: specify which CAIDA 2019 dataset (date, duration, anonymization level), number of packets, and replay parameters. The phrase "volume of input elephant flows is selectively adjusted to 50, 100, and 150" is ambiguous; if these are k values, state so explicitly.
  4. [Table 1] No confidence intervals or standard deviations are reported despite the statement that each experiment was run 10 times; these should be added.
  5. [Algorithm 1] The symbol p.exp_seq is undefined; presumably it should be p.seq or a payload-aware expected sequence. Also, notation is inconsistent between "VOTE_THRE" and "VOTE THRE" in the prose and pseudocode.
  6. [References] Several references appear incomplete or with placeholder author lists (e.g., [13], [14]). Please verify and complete all bibliographic entries.

Circularity Check

1 steps flagged · score 2.0 of 10

Priority-recall metric is self-confirmatory (pre-inserted flows are counted unconditionally), but the rest of the evaluation is external-benchmark based; no broader circularity.

  1. self definitional [Section III.A and Section V.A/C (Algorithm 1 priority path, Table 1)]
    ""the 5-tuple of each priority flow must be inserted into the priority table through the controller" (III.A); "10 priority flows will be selected from the unchosen heavy flow" (V.A); Algorithm 1: "if k ∈ priority table then pkt cnt←pkt cnt + 1; ... return"."

    Priority packet recall is measured only on flows that are pre-inserted into the BPF_HASH priority table. For those flows, Algorithm 1 routes every matching packet to an unconditional counter and returns, so 100% priority packet recall is a logical consequence of the test setup, not an independent empirical finding. The headline 'lossless tracking of high-priority flows' is thus validated under an oracle that guarantees the precondition; the paper's own statement 'a major challenge arises in acquiring the complete five-tuple details in advance' (III.A) acknowledges that the general live-traffic case is not addressed. This is a self-definitional evaluation of the priority feature rather than a derivation-based circularity in the algorithmic claims.

full rationale

The paper makes no derivation-style predictions: the top-k detection accuracy, retransmission recall, cardinality estimates, CPU load, and throughput degradation are all measured against external CAIDA ground truth or a direct baseline, so those results are not circular. The Count-Min sketch and linear-counter formulas are standard and used without modifying them to fit the result. The only self-confirmatory element is the priority-table recall: because the evaluation installs priority flows into the BPF_HASH map before replay, and Algorithm 1 counts every matching packet unconditionally, the 100% priority packet recall is an identity of the priority path rather than a discovered property. This does not invalidate the architecture, but it means the headline 'lossless' claim is conditional on the controller knowing flow 5-tuples in advance. I also flag the paper's explicit limitations: Section III.A states 'In the camera-ready version, we will clarify the original rationale of our controller module,' an admitted missing design detail; Section V.D says the complete experimental pipeline will be added later, limiting independent reproduction; and the retransmission threshold (3 ms) and VOTE_THRE are hand-set with no sensitivity analysis, which is parameter dependence rather than circularity. The single self-citation [5] supports only background motivation, not the central derivation. Weighing these, the scoring reflects minor circularity confined to the priority-recall demonstration; the rest of the evaluation is independently grounded.

Assumptions & free parameters 5 free parameters · 6 assumptions · 0 invented entities

No new physical entities are introduced; the priority table is a conventional BPF hash map. The load-bearing choices are hand-set thresholds and array sizes, plus the domain assumption that priority flows can be enrolled before their first packet. The retransmission heuristic is a simplified in-kernel proxy, not an exact detector.

free parameters (5)
  • VOTE_THRE = not specified
    Used in heavy flow table eviction in Algorithm 1; product with negative_counter compared to packet_count. Its value directly affects which flows are evicted and therefore top-k accuracy.
  • Retransmission timestamp threshold (THRE) = 3 ms (example)
    Section III.B requires p.ts - entry.ts >= THRE to classify a packet as retransmission; this threshold separates reordering from retransmission and directly sets retransmission recall.
  • Heavy flow table slot count = not specified
    Fixed-size BPF_ARRAY in Section III.B; collision pressure and top-k accuracy depend on this size, but the value is not reported.
  • CMS array sizes = 3 layers x 500 entries
    Section III.D sets each CMS layer to 500 entries without sensitivity analysis; CMS estimation error depends on width and depth.
  • Linear counter size m = not specified
    The cardinality estimate in Section III.C uses the linear counter formula with array size m; no value or load factor is reported.
assumptions (6)
  • standard math Linear counter estimator -m * ln(V/m) is unbiased for uniformly hashed distinct values
    Invoked in Section III.C; requires near-uniform hashing and m large relative to the true cardinality.
  • standard math Count-Min Sketch minimum-of-three estimate gives a conservative packet count
    Used in Sections III.D and III.E for flow reconstruction; assumes independent hash functions and non-negative update errors.
  • domain assumption BPF_HASH and BPF_ARRAY with __sync_fetch_and_add provide safe concurrent kernel counters
    Section IV relies on atomic primitives and the netif_receive_skb tracepoint; any missed packet at the tracepoint would break the "lossless" priority tracking claim.
  • domain assumption Replaying a CAIDA 2019 trace on a direct-connected VM link at original pace reproduces a 10 Gbps production workload
    Section V.A setup; no packet loss, reordering, or latency variability is induced, so retransmission and hash-collision behavior may differ in real networks.
  • ad hoc to paper Priority flow 5-tuples are known and installed before traffic starts
    Section III.A: "the five-tuple of each priority flow must be inserted into the priority table through the controller." This premise makes priority recall 100% in the evaluation, but it is not generally available in live traffic.
  • ad hoc to paper Sequence-number decrease with timestamp gap >= 3ms identifies retransmission
    Section III.B heuristic; it assumes no TCP reordering events with delay >= 3ms, which is not validated.

how reviews work

0 comments
Cite this review

Pith. "Pith review of PSketch: A Priority-Aware Sketch Architecture for Real-Time Flow Monitoring via eBPF." pith.science (2026). https://pith.science/paper/OL5HKFY2

@misc{pith2026250907338,
  author       = {Pith},
  title        = {Pith review of: PSketch: A Priority-Aware Sketch Architecture for Real-Time Flow Monitoring via eBPF},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OL5HKFY2}},
  note         = {Machine review of arXiv:2509.07338}
}
read the original abstract

Sketch-based monitoring in SDN often suffers from tightly coupled pipeline and memory constraints, limiting algorithmic flexibility and reducing accuracy. We propose PSketch, the first in-kernel priority-aware sketching framework implemented with eBPF. It ensures lossless tracking of high-priority flows via a hash-based table and approximates top-k elephant flows using a sketch pipe. PSketch supports both TCP and UDP and enables in-kernel retransmission tracking with minimal overhead. Unlike SDN-based approaches, it runs on commodity Linux systems, removing hardware dependencies. We perform evaluation on 10 Gbps CAIDA traces. Results show that PSketch achieves 96.0% top-k detection accuracy, 96.4% retransmission recall, and only 0.7% throughput degradation.

Figures

Figures reproduced from arXiv: 2509.07338 by the authors.

Figure 1
Figure 1. Architecture of PSketch [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Sketchvisor: Robust network measurement for software packet pro- cessing,

    Q. Huang, X. Jin, P. P. Lee, R. Li, L. Tang, Y .-C. Chen, and G. Zhang, “Sketchvisor: Robust network measurement for software packet pro- cessing,” inProceedings of the Conference of the ACM Special Interest Group on Data Communication, 2017, pp. 113–126

  2. [2]

    A robust counting sketch for data plane intrusion detection,

    S. Kim, C. Jung, R. Jang, D. Mohaisen, and D. H. Nyang, “A robust counting sketch for data plane intrusion detection,” in30th Annual Network and Distributed System Security Symposium, NDSS 2023. The Internet Society, 2023

  3. [3]

    Aiacc-training: Optimizing distributed deep learning training through multi-streamed and concurrent gradient communications,

    L. Lin, S. Qiu, Z. Yu, L. You, L. Xin, X. Sun, J. Xu, and Z. Wang, “Aiacc-training: Optimizing distributed deep learning training through multi-streamed and concurrent gradient communications,” in2022 IEEE 42nd International Conference on Distributed Computing Systems (ICDCS). IEEE, 2022, pp. 853–863

  4. [4]

    Beyond data and model parallelism for deep neural networks,

    Z. Jia, M. Zaharia, and A. Aiken, “Beyond data and model parallelism for deep neural networks,” inProceedings of the 2nd Conference on Machine Learning and Systems (MLSys), 2019

  5. [5]

    Dnn architecture attacks via network and power side channels,

    Y . Dai, Q. Guo, and A. Wang, “Dnn architecture attacks via network and power side channels,” inInternational Conference on Security and Privacy in Communication Systems. Springer, 2023, pp. 63–87

  6. [6]

    Elastic sketch: Adaptive and fast network-wide measurements,

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

  7. [7]

    Mc-sketch: Enabling heterogeneous net- work monitoring resolutions with multi-class sketch,

    K. C.-J. Lin and W.-L. Lai, “Mc-sketch: Enabling heterogeneous net- work monitoring resolutions with multi-class sketch,” inIEEE INFO- COM 2022-IEEE Conference on Computer Communications. IEEE, 2022, pp. 220–229

  8. [8]

    The design and operation of cloudlab,

    D. Duplyakin, R. Ricci, A. Maricq, G. Wong, J. Duerig, E. Eide, L. Stoller, M. Hibler, K. Webb, D. Johnson, L. Kasper, A. Akella, K. Atkinson, A. Bavier, J. Albrecht, J. B. Edwards, M. J. Freedman, G. Gibb, M. Hajiaghayi, C. Hibler, D. Z. Tennenhouse, and R. van Renesse, “The design and operation of cloudlab,” inProceedings of the 2019 USENIX Annual Techn...

Show all 27 references
  1. [9]

    Google cloud platform,

    Google Cloud, “Google cloud platform,” https://cloud.google.com/, 2025, accessed: 2025-06-28

  2. [10]

    Ohio Supercomputer Center,

    Ohio Supercomputer Center, “Ohio Supercomputer Center,” 1987, https://www.osc.edu. [Online]. Available: https://www.osc.edu

  3. [11]

    Geni: A federated testbed for innovative network experiments,

    M. Berman, J. S. Chase, L. Landweber, A. Nakao, V . Thomas, R. Ricci, G. Wong, and C. Elliott, “Geni: A federated testbed for innovative network experiments,”Computer Networks, vol. 61, pp. 5–23, 2014. [Online]. Available: https://doi.org/10.1016/j.comnet.2013.12.037

  4. [12]

    The caida ucsd anonymized internet traces 2019,

    CAIDA: Center for Applied Internet Data Analysis, “The caida ucsd anonymized internet traces 2019,” Available at: https://www.caida.org/ catalog/datasets/passive dataset/, accessed: 2025-06-29

  5. [13]

    Fast and memory-efficient sketches in the ebpf virtual machine,

    S. Mianoet al., “Fast and memory-efficient sketches in the ebpf virtual machine,” inProceedings of the ACM SIGCOMM 2023 Conference, 2023

  6. [14]

    Kernel-level count-min sketch for ddos detection with ebpf,

    Y . Zanget al., “Kernel-level count-min sketch for ddos detection with ebpf,” inProceedings of the IEEE International Conference on Computer Communications (INFOCOM), 2021

  7. [15]

    Sketchflow: Efficient flow size estimation with hybrid sketches,

    X. Yu, Y . Li, and H. Li, “Sketchflow: Efficient flow size estimation with hybrid sketches,” inProceedings of the IEEE International Conference on Network Protocols (ICNP), 2022

  8. [16]

    Efficient network monitoring applications in the kernel with ebpf and xdp,

    C. Abranches, O. Michel, and C. E. Rothenberg, “Efficient network monitoring applications in the kernel with ebpf and xdp,” inProceedings of the 2021 ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS), 2021

  9. [17]

    A control plane enabling automated and fully adaptive network traffic monitoring with ebpf,

    L. Magnani, N. Bonelli, and G. Bianchi, “A control plane enabling automated and fully adaptive network traffic monitoring with ebpf,” IEEE Transactions on Network and Service Management, vol. 19, no. 4, pp. 4218–4231, 2022

  10. [18]

    ebpfmon: Priority-aware adaptive telemetry with ebpf,

    K. Zhang, J. Liu, and Y . Wang, “ebpfmon: Priority-aware adaptive telemetry with ebpf,” inProceedings of the IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), 2021

  11. [19]

    Network observability with ebpf,

    OpenSource.com contributors, “Network observability with ebpf,” https: //opensource.com/article/22/8/ebpf-network-observability-cloud, 2022, accessed: 2025-08-28

  12. [20]

    Opentelemetry ebpf collector,

    OpenTelemetry Project, “Opentelemetry ebpf collector,” https://github. com/open-telemetry/opentelemetry-ebpf, 2022, accessed: 2025-08-28

  13. [21]

    Pixie: Kubernetes observability with ebpf,

    Pixie Labs, “Pixie: Kubernetes observability with ebpf,” https://px.dev, 2022, accessed: 2025-08-28

  14. [22]

    Flowradar: A better netflow for data centers,

    Z. Liu, Q. Li, P. Luo, Y . Yu, C. Guo, and Y . Zhang, “Flowradar: A better netflow for data centers,” inProceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2016, pp. 311–324

  15. [23]

    Hardware-based hash functions for network applications,

    F. Yamaguchi and H. Nishi, “Hardware-based hash functions for network applications,” in2013 19th IEEE International Conference on Networks (ICON), 2013, pp. 1–6

  16. [24]

    A linear- time probabilistic counting algorithm for database applications,

    K.-Y . Whang, B. T. Vander-Zanden, and H. M. Taylor, “A linear- time probabilistic counting algorithm for database applications,”ACM Transactions on Database Systems (TODS), vol. 15, no. 2, pp. 208–229, 1990

  17. [25]

    An improved data stream summary: the count-min sketch and its applications,

    G. Cormode and S. Muthukrishnan, “An improved data stream summary: the count-min sketch and its applications,”Journal of Algorithms, vol. 55, no. 1, pp. 58–75, 2005

  18. [26]

    Fabric: A national-scale programmable research infrastructure for computer sci- ence and science applications,

    P. Ruth, I. Baldine, A. Mandal, Y . Xin, I. Baldinet al., “Fabric: A national-scale programmable research infrastructure for computer sci- ence and science applications,” inUSENIX Annual Technical Conference (Poster), 2021

  19. [27]

    Development and pilot testing of an online case-based approach to shared decision making skills training for clinicians,

    R. J. V olk, N. K. Shokar, V . B. Leal, R. J. Bulik, S. K. Linder, P. D. Mullen, R. M. Wexler, and G. S. Shokar, “Development and pilot testing of an online case-based approach to shared decision making skills training for clinicians,”BMC Medical Informatics and Decision Makin...

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.