PaperlayerView exact revision on arXiv

Source-linked AI summary

007: Democratically Finding The Cause of Packet Drops

Behnaz Arzani, Selim Ciraci, Luiz Chamon, Yibo Zhu, Hingqiang Liu, Jitu Padhye, Boon Thau Loo, Geoff Outhred

arXiv:1802.07222v1cs.NI

TL;DR

Datacenter operators need to locate packet-drop causes at both link and TCP-connection granularity, but existing monitoring leaves important failures unexplained. 007 is an always-on, end-host system that traces retransmitting flows and ranks their path links by proportional blame. It detects problems found by prior tools while also identifying previously undetected sources, and can identify drop rates as low as 0.05%.

  • Problem

    007 addresses the need to find which link caused each TCP-flow packet drop without changing network infrastructure, especially where existing tools cannot explain application-impacting failures.

    Source: §1 · p. 1

  • Method

    007 monitors TCP retransmissions, discovers affected flows’ paths, and ranks path links using proportional blame votes.

    Source: §1 · p. 1, §2 · p. 3

  • Results

    007 found every problem identified by previously deployed monitoring tools while also finding sources they missed; it identified drop rates as low as 0.05% in datacenters with thousands of links.

    Source: §1 · p. 2, §11 · p. 13

  • Takeaways & Limitations

    007 provides flow-level application context for diagnosing problematic links using an always-on end-host deployment with negligible overhead.

    Source: §1 · p. 1, §9 · p. 10

    The rate-control analysis assumes a Clos topology and uniformly random communication between hosts under different top-of-rack switches.

    Source: §4.1 · p. 3

Abstract

from arXiv · show

Network failures continue to plague datacenter operators as their symptoms may not have direct correlation with where or why they occur. We introduce 007, a lightweight, always-on diagnosis application that can find problematic links and also pinpoint problems for each TCP connection. 007 is completely contained within the end host. During its two month deployment in a tier-1 datacenter, it detected every problem found by previously deployed monitoring tools while also finding the sources of other problems previously undetected.

1 Introduction

007 targets packet-drop diagnosis at link and TCP-connection granularity without network-infrastructure changes or significant overhead. Its design combines end-host monitoring, path-aware blame assignment, theoretical guarantees, and datacenter deployment experience.

1 Introduction

  • 17% of VM reboots are due to network issues, and existing monitoring tools locate the causing links in fewer than 30% of those cases.The paper motivates connection-level diagnosis because network failures can severely affect applications despite limited visibility from traditional monitoring.Source: §1 · p. 1
  • Existing approaches leave coverage, scalability, infrastructure, or application-context gaps: Pingmesh can miss failures, Roy et al. require router changes, and Everflow is not scalable.Operators need to correlate customer impact and bad links, which these systems do not directly provide.Source: §1 · p. 1
  • 007 finds likely drop causes for individual TCP flows by recording retransmitting flows’ paths and assigning proportional blame to their links.Aggregated votes rank links by relative drop rates, connecting problematic links to affected connections.Source: §1 · p. 1
  • 007 requires no network-infrastructure or client-software changes, detects in-band failures, tolerates noise, and has negligible overhead.The monitoring agent runs independently at the end host rather than modifying switches or clients.Source: §1 · p. 1
  • 007’s two-month deployment found every problem detected by existing monitoring tools and also identified sources of problems those tools did not explain.The authors additionally claim theoretical accuracy under noise and practical deployment solutions.Source: §1 · p. 2

2 Motivation

007 uses TCP retransmissions as in-band evidence of packet loss, avoiding dedicated probes and large-scale traffic capture. Production observations motivate tracking only selected flows and ranking links with a simple voting scheme.

2 Motivation

  • 007 identifies retransmission causes, targets scalable and minimally disruptive datacenter deployment, focuses on infrastructure traffic, deliberately includes congestion-induced retransmissions, and flags even short-lived congestion while accounting for noise.Source: §2 · p. 2
  • TCP retransmissions provide detectable loss signals, allowing 007 to use data traffic as probes instead of tagging every packet or deploying special switch infrastructure.This leverages TCP’s connection-oriented reliable-delivery behavior while introducing little monitoring overhead.Source: §2 · p. 2
  • Optimization-based approaches are NP-hard, tracking every flow path is not scalable, and traceroute-based discovery is constrained by switch control-plane limits.These constraints motivate a lightweight selective-tracking design.Source: §2 · p. 2
  • 95% of intervals with at least 10 total drops contain drops on at least 3 flows, while in at least 80% of cases no flow contains more than 34% of drops.These observations support distributing blame across multiple paths rather than attributing all drops to one connection.Source: §2 · pp. 2–3
  • 007 assigns each link on a retransmitting flow’s path a vote of 1/h, then sums votes to rank links by likely drop rates.The ranking produces a network heat map tied to application or customer impact.Source: §2 · p. 3

3 Design Overview

007 is an end-host application with separate agents for detecting TCP retransmissions, discovering flow paths, and analyzing link blame. It periodically aggregates path-based votes while maintaining low resource use.

3 Design Overview

  • 007 runs as a user-level process on each end host and comprises TCP-monitoring, path-discovery, and analysis agents.The architecture is deployed alongside other applications rather than embedded in network devices.Source: §3 · p. 3
  • A retransmission triggers path discovery for the affected flow, after which a centralized analysis agent tallies link votes every 30 seconds.Failures need not last for the full aggregation interval.Source: §3 · p. 3
  • Production resource use is low: memory stays below 600 KB per host, CPU utilization is 1–3%, and traceroute bandwidth reaches at most 200 KBps per host.The implementation contains about 6000 lines of C++ code and is proven accurate under typical datacenter conditions.Source: §3 · p. 3

4 The Path Discovery Agent

The path-discovery agent traces only retransmitting flows while controlling ICMP load and matching traceroute packets to the original ECMP path. It handles load balancing, partial traces, rerouting, and concurrent probing in practice.

4.1 ICMP Rate Limiting

  • 007 limits traceroute generation so switch ICMP responses stay below Tmax = 100 per second, using Ct = 10 as the host-side threshold in the authors’ datacenters.The design also limits each connection to one path-discovery trigger per epoch.Source: §4.1 · pp. 3–4
  • Only 2.1% of monitored flows traversed tier-3 switches, enabling the rate analysis to ignore those switches under the stated Clos-topology and uniform-traffic assumptions.The rate guarantee depends on the assumed topology and traffic distribution.Source: §4.1 · p. 3

4.2 Engineering Challenges

  • Traceroute packets use the flow’s five-tuple and the load balancer’s DIP mapping so ECMP sends them along the same path as data packets.Connections established through a VIP must be translated to the physical destination IP before tracing.Source: §4.2 · p. 4
  • If a high-drop link or blackhole interrupts traceroute, partial traces can directly pinpoint the faulty link and remain usable by the analysis engine.This turns some traceroute failures into useful diagnostic evidence.Source: §4.2 · p. 4
  • Path matching remains likely when routing is stable for a few milliseconds because retransmission and path-discovery delays are typically below a millisecond after datacenter RTTs of 1–2 ms.The paper notes that prior work found such short-term path stability usually holds.Source: §4.2 · p. 4
  • The implementation sends 15 crafted TCP packets with TTLs from 0–15, encodes TTLs in IP IDs, and uses bad checksums to avoid disturbing live connections.These choices support concurrent traceroutes and isolate probes from ongoing traffic.Source: §4.2 · p. 4

5 The Analysis Agent

007’s analysis agent uses voting to rank likely problematic links from retransmission evidence, with theoretical guarantees under noise and optimization-based benchmarks for comparison.

5.1 Voting-Based Scheme

  • 007 votes each flow’s path when a retransmission occurs, then tallies votes per epoch to rank links as likely causes of drops.Good votes are 0, while each link on a retransmitting flow’s path receives 1/h, where h is the path length.Source: §5.1 · pp. 4–5
  • A 1% vote threshold identifies problematic links, while topology-aware iterative adjustment reduces false positives by 5%.Higher thresholds reduce false positives but increase false negatives.Source: §5.1 · p. 5
  • 007 focuses on detecting failed links, while switch-failure detection is possible by voting on switches but remains outside this work’s scope.Source: §5.1 · p. 5

5.2 Voting Scheme Analysis

  • The analysis addresses noise from sporadic drops on good links, which can cause inaccuracies even though 007’s error likelihood is shown to be small.The theoretical conditions are sufficient but not necessary, and later evaluation examines performance when they do not hold.Source: §5.2 · p. 5
  • Under mild conditions, higher-drop-rate links rank higher, enabling 007 to identify each flow’s most likely drop cause; error probability decreases exponentially with the number of flows.With low enough non-failed-link drop probability, 007 can identify failed links with high probability.Source: §5.2 · p. 5

5.3 Optimization-Based Solutions

  • The voting scheme is compared with NP-hard binary and integer optimization programs, and 007 outperforms the binary benchmark by more than 50% under noise.The integer program uses retransmission counts to rank links and performs better than the binary program, but both are used as benchmarks.Source: §5.3 · p. 6

6 Evaluations: Simulations

Simulations show that 007 accurately localizes per-flow drops and failed links across conservative and adverse conditions, generally outperforming the optimization baseline. Its accuracy remains strong under noise, variable traffic, multiple failures, and larger networks, with identifiable degradation only in extreme cases.

6.1 In The Optimal Case

  • 007 achieves average accuracy above 96% in almost all optimal-case settings and detects low-rate failed links with high recall and precision.Under the stated Theorem 2 conditions, it also outperforms the optimization in most cases because of its robustness to noise.Source: §6.1 · pp. 6–7, Figure 3 · p. 7, Figure 4 · p. 7

6.2 Varying Drop Rates

  • 007 remains highly accurate below Theorem 2’s conservative drop-rate bounds, including single failures and multiple failures with heavily different drop rates.The experiments specifically test conditions where prior work reported difficulty detecting failures with unequal drop rates.Source: §6.2 · p. 7

6.3 Impact of Noise

  • 007 shows little sensitivity to increased noise when identifying per-flow drop causes, while the optimization is highly noise-sensitive.This comparison is reported for both single-failure and five-failure settings.Source: §6.3 · p. 7, Figure 6 · p. 7

6.4 Varying Number of Connections

  • With 10–60 connections per epoch, 007 accurately identifies per-flow causes and maintains high-probability detection regardless of the number of failures.The optimization becomes underconstrained at low drop rates and with multiple failures, producing large variance.Source: §6.4 · p. 7, Figure 7 · p. 8

6.5 Impact of Traffic Skews

  • Under skewed traffic, 007 detects causes with probability ≥85% above 0.1% drop rates and maintains a detection rate of ≥98% with multiple failures.It tolerates up to 50% of flows targeting one hot ToR with negligible accuracy degradation, but higher skew can hurt accuracy with at least 10 failures.Source: §6.5 · pp. 7–8, Figure 8 · p. 8

6.6 Detecting Bad Links

  • For failed-link detection, 007 outperforms the optimization and detects up to 7 heavily skewed failures with accuracy above 90%.Recall declines as failures increase because other links accumulate votes and raise the cutoff threshold; selecting the top k links would bring recall close to 100%.Source: §6.6 · p. 8, Figure 10 · p. 8, Figure 11 · p. 8

6.7 Effects of Network Size

  • 98%, 92%, 91%, and 90% average accuracy across networks with 1, 2, 3, and 4 pods, versus 94%, 72%, 79%, and 77% for the optimization.Algorithm 1 maintains recall ≥98% through 6 pods, dropping to 85% at 7 pods, while precision remains 100% for all pod sizes.Source: §6.7 · pp. 8–9
  • With 30 failed links, 007’s per-flow accuracy remains 98.01%, indicating stable performance at high failure counts.This complements the network-size results by testing many simultaneous failed links rather than more pods.Source: §6.7 · p. 9

7 Evaluations: Test Cluster

In a controlled test cluster, 007 localized failures on individual flows and ranked failed links using retransmission-derived path evidence. It remained effective across clean-testbed anomalies, unequal and multiple link failures, while keeping false positives lower than the compared optimization.

7.1 Clean Testbed Validation

  • In a clean cluster, abnormal average votes of 22.5±3.65 on links entering one ToR fell to zero after rebooting the suspected switch.This validated the suspicion and showed sensitivity to low-rate problems.Source: §7.1 · p. 9

7.2 Per-connection Failure Analysis

  • 007 correctly attributed 90.47% of eligible drops to the higher-rate link when two links dropped packets at 0.2% and 0.05%.Source: §7.2 · p. 9

7.3 Identifying Failed Links

  • At 1% and 0.1% drop rates, the failed link ranked highest; at 0.05%, it ranked highest in 88.89% of instances but always among the top two.The lower-rate case became harder because lone drops on healthy links narrowed the vote gap.Source: §7.3 · p. 9, Figure 13 · p. 9
  • The optimization matched the correct result every time but marked 1.5, 1.18, and 1.47 times as many links as 007 at 1%, 0.1%, and 0.05%.Source: §7.3 · p. 9
  • 007 identified all failed links 80% of the time with one allowed false positive under skewed traffic, and identified each connection’s true cause 98% of the time.With two failures at 0.2% and 0.1%, the higher-drop link ranked first every time, while the second remained among the five highest-voted links.Source: §7.3 · p. 9

8 Evaluations: Production

Production evaluations tested 007’s monitoring overhead, per-connection diagnosis, and explanations for previously unexplained VM reboots. 007 found known and previously undetected problems while matching Everflow’s link diagnoses in the tested flows.

8 Evaluations: Production

  • 007 found every problem caught by previously deployed diagnosis tools and additionally identified power, FCS, reconfiguration, BGP, link-flap, and software problems.Source: §8 · p. 10

8.1 Validating Theorem 1

  • The number of ICMP messages generated by 007 never exceeded the per-switch limit Tmax.The production table reports max(T) ≤ Tmax.Source: §8.1 · p. 10, Table 1 · p. 10

8.2 TCP Connection Diagnosis

  • 007 matched Everflow’s dropped-link diagnosis in every tested case, and every recorded path matched the flow’s captured path exactly.Everflow captured all outgoing IP traffic from nine hosts for five hours, after which retransmitting flows were compared.Source: §8.2 · p. 10

8.3 VM Reboot Diagnosis

  • 007 identified a link for all 281 previously unexplained VM reboots; 262 involved transient host-to-ToR drops, while others involved ToR drops, configuration updates, or link flaps.Source: §8.3 · p. 10
  • Across one cluster and one day, 007 identified 0.45±0.12 packet-dropping links per epoch, with a maximum vote tally averaging 2.51±0.33.Among identified failures, 48% were server-to-ToR links, 24% T1-to-ToR links, and 6% T2-to-T1 failures.Source: §8.3 · p. 10

9 Discussion

The discussion explains where 007’s diagnosis applies and which assumptions shape its accuracy and overhead. It treats common low-rate congestion as noise while using vote counts to prioritize potentially actionable failures.

9.1 007’s Main Assumptions

  • 007 assumes retransmissions usually reflect forward-path drops, connections bypass SNAT, and paths can be discovered outside L2-only routing.Severe reverse-path loss, spurious timeout retransmissions, SNAT, and L2 networks require the stated qualifications or alternatives.Source: §9.1 · p. 10
  • Higher path diversity improves accuracy, while an ICMP rate limit can prevent diagnosis for flows whose paths were not identified even though link localization remains accurate.The system accepts this accuracy trade-off for simpler operation and lower overhead.Source: §9.1 · p. 11

9.2 Other Factors To Consider

  • 007 treats prevalent congestion with drop rates 10^-8–10^-5 as noise, but retains major congestion events because they signal severe imbalance or incast and are actionable.Its ranking intentionally favors frequently used failed links to prioritize high-impact failures.Source: §9.2 · p. 11
  • 007 is designed for infrastructure connections and application context; extending it to customer-VM TCP failures would introduce security issues and remains future work.Source: §9.2 · p. 11
  • Vote tallies explain packet-drop causes, but many identified drops are not actionable and do not require operator intervention.The tally is a starting point for deciding when intervention is needed.Source: §9.2 · p. 11

10 Related Work

007 differs from prior diagnosis and tomography systems by using ongoing TCP traffic and targeted path discovery rather than pervasive probing, packet capture, or infrastructure changes. It therefore emphasizes always-on, flow-level localization under practical datacenter constraints.

10 Related Work

  • Unlike, 007 requires no router or endpoint modifications, diagnoses individual connections, and handles multiple simultaneous failures while limiting path discovery to needed flows.Source: §10 · p. 11
  • Everflow can identify packet paths accurately but is not scalable as an always-on system and requires switch features, whereas 007 uses lightweight ongoing monitoring.Source: §10 · p. 12
  • Probe-based inference such as Pingmesh samples connectivity and can miss fine-timescale failures, while 007 provides always-on monitoring from ongoing traffic.Pingmesh’s probe interval is described as five minutes.Source: §10 · pp. 11–12
  • Network tomography approaches generally gather large traffic volumes and are better suited to non-transient failures, whereas 007 handles transient and persistent errors across the infrastructure.Source: §10 · p. 12
  • TCP-statistics approaches such as [61] lack continuous monitoring or scale poorly, while 007 targets the responsible link for each TCP connection.Source: §10 · p. 12
  • 007 complements failure-resilience, failure-analysis, and anomaly-detection work by locating problematic devices that those systems can avoid or analyze further.Source: §10 · p. 12

11 Conclusion

007 is an always-on, scalable datacenter diagnosis system that identifies low-rate packet drops through ongoing TCP flows. Its deployment and examples show practical value for unexplained VM reboots and link localization.

11 Conclusion

  • 007 identifies drop rates as low as 0.05% in datacenters with thousands of links by monitoring ongoing TCP flows.Source: §11 · p. 13

A Application example: VM reboots

B Network tomography example

C Proofs

The proofs analyze monitoring and traceroute behavior in a Clos datacenter topology under uniform routing and independent failures. They bound per-link probe rates by the larger rate for level 1 or level 2 links.

C Proofs

  • The Clos model contains pods of ToR switches connected through tier-1 and tier-2 switches, with level 1 and level 2 links defined by these connections.Source: C Proofs · p. 16, Figure 15 · p. 16
  • The analysis assumes uniformly random cross-ToR connections, independent routing and failures, and independent packet drops across links and packets.Source: C Proofs · p. 16

C.1 Proof of Theorem 1

  • Traceroute rates depend on whether a link is level 1 or level 2 because routing probabilities are uniform within each level.Source: §C.1 · p. 16
  • The ICMP rate at every link is bounded by T ≤ max[n0R1,n1R2], yielding the stated network-wide probe-rate bound.Source: §C.1 · p. 16

C.2 Proof of Theorem 2

Theorem 2 connects link retransmission probabilities to voting accuracy in a Clos topology, while the accompanying proof decomposes voting events and bounds good-link noise. The section also formalizes the NP-hard alternative and its greedy approximation.

C.2 Proof of Theorem 2

  • In the typical datacenter case, where n0 ≥ 2n2 and the stated ratio condition holds, the required number of pods reduces to a simpler bound.Source: §C.2 · pp. 17, 20
  • If rb ≥ αrg under the stated Clos-topology conditions, a bad link receives votes with higher probability than a good link.Source: §C.2 · p. 18
  • The proof relates retransmission probabilities to packet-drop rates using r = 1−(1−p)c and bounds based on lower and upper connection sizes.Source: §C.2 · pp. 17–18
  • The proof models bad and good link votes as binomial variables and uses a union bound plus large-deviation bounds involving Kullback-Leibler divergence.Source: §C.2 · pp. 17–18
  • A link receives a vote when a connection traverses it and a retransmission occurs, with level-specific events decomposed across the Clos path.Source: §C.2 · pp. 19–20

D Greedy solution of the binary program

Related papers

Loading 1802.07222v1…