Source-linked AI summary
PINT: Probabilistic In-band Network Telemetry
Ran Ben Basat, Sivaramakrishnan Ramanathan, Yuliang Li, Gianni Antichi, Minlan Yu, Michael Mitzenmacher
TL;DR
INT provides useful network visibility but imposes packet overhead that can degrade flow completion time and application-level goodput. PINT addresses this by probabilistically encoding telemetry across multiple packets under a user-set per-packet bit budget, and it supports concurrent use cases with sixteen bits per packet and comparable state-of-the-art performance. Its effectiveness is constrained by the available bit budget, network diameter, and flows too short to provide multiple packets.
Problem
INT’s per-packet overhead grows with path length and telemetry volume, degrading flow completion time and application-level goodput.
Method
PINT probabilistically distributes requested telemetry across multiple packets and coordinates concurrent queries within a user-specified per-packet bit budget.
Results
PINT concurrently supports path tracing, congestion control, and median/tail latency estimation using sixteen bits per packet, with performance comparable to the state of the art.
Takeaways & Limitations
PINT provides similar visibility to INT while bounding packet overhead, enabling several telemetry applications under a fixed per-packet budget.
Takeaways & Limitations
PINT is less effective for single-packet short flows, and its resilience depends on the per-packet bit budget and network diameter.
Abstract
from arXiv · showhide
Commodity network devices support adding in-band telemetry measurements into data packets, enabling a wide range of applications, including network troubleshooting, congestion control, and path tracing. However, including such information on packets adds significant overhead that impacts both flow completion times and application-level performance. We introduce PINT, an in-band telemetry framework that bounds the amount of information added to each packet. PINT encodes the requested data on multiple packets, allowing per-packet overhead limits that can be as low as one bit. We analyze PINT and prove performance bounds, including cases when multiple queries are running simultaneously. PINT is implemented in P4 and can be deployed on network devices. Using real topologies and traffic characteristics, we show that PINT concurrently enables applications such as congestion control, path tracing, and computing tail latencies, using only sixteen bits per packet, with performance comparable to the state of the art.
1 INTRODUCTION
PINT preserves the visibility benefits of in-band telemetry while bounding per-packet overhead, potentially to one bit. It probabilistically spreads requested information across packets and supports concurrent telemetry applications with sixteen bits per packet and comparable state-of-the-art performance.
- PINT bounds per-packet telemetry overhead to a user-defined value, as low as one bit, while providing visibility similar to INT.It relies on approximations because many consuming applications do not require every per-packet-per-hop value.
- PINT probabilistically encodes requested information across multiple packets, so a flow’s packet collection provides the relevant data.Unlike INT, which has each switch embed its own information in every packet, PINT spreads information across packets.
- PINT supports several concurrent queries while keeping cumulative per-packet overhead within the user-specified budget.The framework assigns each packet a query subset whose combined overhead remains within that budget.
- PINT is implemented on commercial programmable switches using P4 and evaluated for path tracing, congestion control, and median/tail latency estimation.The evaluation uses real topologies and traffic characteristics.
- 16 bits per packet enables the three use cases concurrently with performance comparable to the state of the art.
2 INT AND ITS PACKET OVERHEAD
INT adds metadata that grows with telemetry values and path hops, consuming packet capacity and potentially degrading application and switch performance. Experiments show that larger overheads substantially worsen flow completion time and long-flow goodput, while jumbo frames do not broadly remove the constraint.
- INT metadata overhead grows linearly with the number of telemetry values and path hops.A five-hop topology requires at least 28 bytes for one metadata value per device, while HPCC’s three values per hop produce around 6.8% overhead.
- Additional INT bits consume payload capacity within the MTU, potentially forcing messages such as RPC calls onto multiple packets.
- 48 bytes of overhead increases average flow completion time by 10% and degrades long-flow goodput by 10% at approximately 70% network utilization.
- 108 bytes of overhead increases flow completion time by 25% and degrades goodput by 20% at approximately 70% network utilization.
- Jumbo frames mitigate INT overhead in some data center networks, but they are unavailable in many networks and some protocols, including RDMA over Converged Ethernet, use a 1KB MTU.
- INT overhead also increases packet processing time at switches because bits must be converted between serial and parallel forms at interfaces.This affects both input and output interfaces of every switch traversed by the packet.
3 THE PINT FRAMEWORK
PINT supports bounded-overhead telemetry by aggregating values, probabilistically distributing query execution across packets, and coordinating switches without adding telemetry headers. Its framework defines query budgets, transparent recording and inference, concurrent execution, and several practical design challenges.
- Aggregation Operations: PINT supports per-packet, static per-flow, and dynamic per-flow aggregation for summarizing path values, fixed flow-switch values, or per-switch packet-value streams.Examples include max/min/sum over a packet’s path, switch-path inference from static IDs, and median latency over packet streams.
- Query Specification: Each query specifies values, aggregation type, bit-budget, optional space-budget, flow definition, and frequency.The bit-budget can preserve fixed packet sizing and help avoid exceeding the network MTU.
- Bounded Overhead: PINT encodes requested information probabilistically across multiple packets, keeping each packet’s overhead within its query or global budget.A global 16-bit digest can carry multiple query digests, such as two concurrent 8-bit queries.
- System Architecture: PINT Source adds the user-sized digest, switches modify it without adding bits, and PINT Sink removes it for recording and optional inference.The destination receives the data packet after digest removal, while recorded data is processed outside the switches.
- Query Engine: The Query Engine compiles a probability distribution over query sets, and all switches use the same packet-level choice without adding a telemetry header.A global hash function coordinates switch decisions while the digest is modified along the path.
- Design Challenges: Design challenges include representing large values within bit limits and coordinating switches without increasing packet overhead.The framework also avoids storing per-flow state on switches and reduces sink-to-analysis traffic by logging fewer bytes than INT.
4 AGGREGATION TECHNIQUES
PINT reduces telemetry overhead through probabilistic coordination, distributed encoding, and compression while supporting aggregation and concurrent queries. Its coding schemes distribute information across packets and provide decoding guarantees under different traffic and path conditions.
- Implicit Coordination via Global Hash Functions: Global hash functions coordinate query selection and switch outcomes without communication, using packet identifiers shared across switches and the Inference Module.All switches apply the same hash to agree on the query executed by each packet.
- Dynamic Per-flow Aggregation: Each packet samples a hop uniformly, giving every hop approximately z/k samples with probability 1 − e^−Ω(z/k).This distributed sampling supports dynamic per-flow aggregation across packets.
- Dynamic Per-flow Aggregation: After O(kε−2) packets, PINT estimates each hop’s (ϕ±ε)-quantile using O(kε−1) space.The guarantee applies to a fixed error target ε and target quantile ϕ.
- Dynamic Per-flow Aggregation: After O(kε−2) packets, PINT recovers values appearing in at least a θ-fraction of samples while excluding values below θ−ε.The guarantee is provided independently for each hop.
- Distributed Coding Schemes: The fully distributed encoding scheme lets stateless encoders modify packet digests without communication, despite each switch holding only one message block.The receiver decodes a k-block message from packets traversing the encoders.
- Distributed Coding Schemes: The Baseline scheme has a long decoding tail because the chance of obtaining a missing block decreases as more blocks are collected.XOR becomes more effective later because recovery requires all but one xor-ed block to be known.
- Distributed Coding Schemes: The multi-layer scheme decodes a message after k log log^*k(1+o(1)) packets, while interleaving Baseline and XOR improves decoding tails.For k=25, the interleaved scheme achieves a median of 41 packets and a 99th percentile of 68 packets.
5 IMPLEMENTATION
PINT’s implementation maps its telemetry use cases onto programmable-switch pipeline stages and parallelizes independent queries to fit stage limits. The path tracing, latency, and congestion-control applications use distinct processing sequences.
- Implementation: PINT is implemented in P4 and can be deployed on commodity programmable switches.The implementation describes how each supported use case executes in the switch pipeline.
- Path Tracing: Path tracing uses four pipeline stages to choose a layer, compute the global hash outcome, hash the switch ID, and write the digest.Additional hashes for a query can execute in parallel because they are independent.
- Latency Aggregation: Median and tail-latency computation uses four stages for latency calculation, compression, hash computation, and conditional value overwriting.Compression adapts the latency value to the query’s bit budget.
- Congestion Control: The HPCC adaptation uses six stages for link-utilization computation, followed by approximation and digest writing.The update may need to occur in one stage; otherwise, the implementation proposes storing recent values.
- Concurrent Queries: Independent queries are processed in parallel to address limited switch pipeline stages when combining the three use cases.The system writes query results to a packet vector and concurrently computes the query subset.
6 EVALUATION
PINT is evaluated for congestion control, latency estimation, and path tracing across realistic workloads and topologies. The results show low-overhead operation, strong path-decoding efficiency, and near-baseline concurrent performance.
- 6.1 Congestion Control: 8 bits per packet yields slowdown similar to HPCC, with better performance on long flows and slightly worse performance on short ones.PINT’s long-flow advantage is attributed to bandwidth savings.
- 6.1 Congestion Control: 71% goodput improvement is achieved at 70% network load for flows over 10MB using PINT.
- 6.1 Congestion Control: p = 1/16 causes only slight performance degradation because approximately 9.4 packets per RTT still carry feedback.The experiment compares p = 1, 1/16, and 1/256 packet fractions.
- 6.1 Congestion Control: Lower feedback frequency affects convergence speed, while stability and fairness remain guaranteed under HPCC’s design and AIMD.
- 6.2 Latency Estimation: Latency-quantile error stabilizes with enough packets and converges toward the error introduced by sketch compression.The evaluation compares 4- and 8-bit budgets with and without KLL sketches.
- 6.3 Path Tracing: 25–36 times fewer packets are needed by PINT with two 8-bit hashes than competing approaches on Kentucky Datalink.PINT is also evaluated with 1-bit and 4-bit budgets against PPM and AMS2.
- 6.4 Concurrent Queries: 0.7% additional median-latency relative error and 0.5% more path-tracing packets are observed in concurrent execution, while long-flow performance does not degrade.The configuration uses an 8-bit budget per query and a 16-bit global budget.
7 LIMITATIONS
PINT’s probabilistic approach is constrained by per-packet bit budget, network diameter, short flows, switch pipeline resources, and multipath routing.
- Tracing short flows: PINT is ineffective for single-packet short flows because it infers paths from multiple packets of the same flow.The paper identifies INT as an alternative for this setting.
- Data plane complexity: Limited programmable-switch pipeline stages may restrict how many additional use cases can be implemented in the data plane.
- PINT becomes more resilient with larger overhead budgets and smaller network diameters.
8 RELATED WORK
Prior telemetry systems either limit visibility through flow selection or incur scalability, state, or packet-overhead costs. PINT instead keeps packet overhead constant rather than linear in path length.
- Selected-flow and sampled-flow approaches are insufficient for applications requiring global visibility, such as path tracing.
- Existing alternatives keep telemetry out-of-band, in switch state, or on packets, each introducing collection, state, or overhead trade-offs.
- Path Dump still imposes overhead linear in path length, whereas PINT keeps packet overhead constant.
9 CONCLUSION
PINT provides INT-like visibility with user-bounded, path-length-independent packet overhead, backed by performance bounds and a P4 implementation. The paper demonstrates this framework across path tracing, congestion control, and latency estimation.
- PINT bounds per-packet overhead to a user-specified constant independent of path length while providing similar visibility to INT.
- The framework is implemented in P4 for deployment on commodity programmable switches.
- Three use cases—path tracing, congestion-control telemetry, and experienced median or tail-latency estimation—are demonstrated using real topologies and traffic characteristics.
A ANALYSIS
This analysis surveys theoretical results underlying PINT’s guarantees, including quantile estimation and sampling requirements. It also accounts for per-flow sketching space and the combined sampling and approximation error.
- Uniformly selected subsets of O(ε^-2s log ε^-1s) elements estimate all possible quantiles within additive error εs.
- PINT requires z = O(kε^-2s) packets for every hop to receive O(ε^-2s) samples with probability 1 −e^-Ω(z/k).
- Separate KLL sketches for k hops require eO(kε^-1a) per-flow storage, with total error ε = εs + εa.
A.2.1 Auxiliary Results.
The auxiliary analysis develops probabilistic bounds for coupon collection and the layered Baseline-XOR encoding scheme. These results establish the packet complexity and success probability of decoding a k-hop path.
- Layered algorithm: The layered algorithm decodes a k-hop path using k log log∗k · (1 + o(1)) packets except with probability δ = e−O(k0.99).The o(1) term hides an additive O(k) term; when d = k, the bound is k log log∗k + e·k + o(k).
- Layered algorithm: The Baseline layer leaves at most k log∗k undecoded hops with probability 1 −δ/6.
- Layered algorithm: Each XOR layer progressively reduces the remaining undecoded hops, and the final layer decodes all remaining hops with probability 1 −δ/6L.
A.2.3 Proof of Part (1).
The proof of Part (1) uses concentration bounds for the number of packets assigned to the Baseline and XOR layers. It shows that the Baseline receives enough packets to support its decoding guarantee.
- Layer 0 is selected with probability 1/2, so Chernoff bounds control the number of packets it receives.
- Applying Lemma 9 with ψ = 1/log∗k bounds the undecoded hops after the Baseline stage by k log∗k with probability 1 −δ/6.
- When at least Ω(k) packets reach the XOR layers, their allocation across levels is analyzed as a balls-and-bins process.
A.2.5 Proof of Part (3).
The proof establishes sampling and decoding guarantees for PINT, including a strict improvement in the packet count required for path decoding. The section also extends PINT to routing-loop detection, trading detection delay for sharply lower false-positive rates.
- With probability 1−δ/6, the algorithm obtains at least Q samples in each layer.
- O(kL log kL) packets suffice to decode the remaining path hops when a digest is XOR-ed by exactly one undecoded hop.
- k · (log log∗k + 1 + o(1)) packets are required under the revised sampling analysis.
- For d = k, path decoding improves from k(log log∗k + e + o(1)) to k(log log∗k + 2 + o(1)).
- 16 bits per packet with T = 1 and b = 15 reduces false loop reports below 5 · 10−7, while T = 3 and b = 14 reduces them to 5 · 10−13.Requiring multiple hash matches increases loop-detection time but prevents the digest from changing after the counter becomes positive.
C ARITHMETIC OPERATIONS IN THE DATA PLANE
The data-plane implementation approximates arithmetic through fixed-point representations, lookup tables, logarithms, and exponentiation. These approximations enable multiplication and division using supported switch operations, but their errors compound across computations.
- Fixed-point representations let switches manipulate fractional values with integer operations such as addition and multiplication.A scale factor is preserved for addition and squared for multiplication, assuming no overflow.
- A lookup table and TCAM identify the leading bits of x to approximate log2(x) with relative error ε < 2−q.The approximation uses the most significant set bit and the next q bits of x.
- The computed logarithm ey lies between log2 x − log2(1 + ε) and log2 x.
- Logarithms in other bases follow from logy x = log2 x/log2 y, with log2(1 + ε) ≤ ε/ln 2 ≈ 1.44 · 2−q.
- Exponentiation is approximated with a 2q-entry lookup table, producing 2x with multiplicative factor 2xε where ε ≤ 2−q.
- Multiplication and division use logarithm addition or subtraction followed by exponentiation, so approximation errors compound across steps.The paper notes that sufficient accuracy at each step is necessary for meaningful results.